我已更正它,但在此测试用例上仍给出错误,其余部分已被接受。!
数字= [1000000000,1000000000,1000000000,1000000000] 目标= -294967296 输出 [[1000000000,1000000000,1000000000,1000000000]] 预期的 []
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> quadriplets = new ArrayList<>();
if (nums.length < 4 || 4 * nums[0] > target || 4 * nums[nums.length - 1] < target){
return new ArrayList<>();
}
for(int i=0;i<=nums.length-4;i++){
if(i==0 || nums[i] != nums[i-1]){
for(int j=i+1;j<=nums.length-3;j++ ){
if(j==i+1 || nums[j] !=nums[j-1]){
int left=j+1 ,right=nums.length-1;
int targetSum=target-nums[i]-nums[j];
while(left<right){
if(nums[left]+nums[right]==targetSum){
List<Integer> quadt= new ArrayList<>();
quadt.add(nums[i]);
quadt.add(nums[j]);
quadt.add(nums[left]);
quadt.add(nums[right]);
quadriplets.add(quadt);
while(left<nums.length-1 && nums[left]==nums[left+1])left++;
while(right>0 && nums[right]==nums[right-1]) right--;
left++;
right--;
}
else if(nums[left]+nums[right] < targetSum){
left++;
}else{
right--;
}
}
}
}
}
}
return quadriplets;
}
}
如果我踩错了一步,请纠正我。
您遇到的问题是由整数溢出引起的。对于示例测试用例,表达式
target-nums[i]-nums[j]
将计算为正数,即使 target
为负数并且 nums[i]
和 nums[j]
为正数。一个快速的解决方案是转换为 long
:
long targetSum=(long)target-nums[i]-nums[j];
这将解决测试用例失败的问题。但测试用例较多,下面的表达式也可能发生溢出:
4 * nums[0] > target || 4 * nums[nums.length - 1] < target
您可以使用
4L
而不是 4
来解决此问题:
4L * nums[0] > target || 4L * nums[nums.length - 1] < target
这个更正后的实现将通过所有测试。