0018. 4Sum - kumaeki/LeetCode GitHub Wiki
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
- 0 <= a, b, c, d < n
- a, b, c, and d are distinct.
- nums[a] + nums[b] + nums[c] + nums[d] == target
- You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Constraints:
- 1 <= nums.length <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
用binary search来查找就好了. 注意越界.
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for(int i = 0, len = nums.length; i < len; i++){
// 如果 i 和 i-1 的数值相同, 那么跳过(结果不重复)
if(i > 0 && nums[i] == nums[i - 1])
continue;
int n1 = nums[i];
for(int j = i + 1; j < len; j++){
// 如果 j 和 j-1 的数值相同, 那么跳过(结果不重复)
if(j > i + 1 && nums[j] == nums[j - 1])
continue;
int n2 = nums[j];
for(int k = j + 1; k < len; k++){
// 如果 k 和 k-1 的数值相同, 那么跳过(结果不重复)
if(k > j + 1 && nums[k] == nums[k - 1])
continue;
// 用long,避免越界
long t = target - n1 - n2 - nums[k];
// binary search
int index = getIndex(nums, t, k + 1, len - 1);
if(index >= 0)
res.add(Arrays.asList(n1 , n2, nums[k], nums[index]));
}
}
}
return res;
}
private int getIndex(int[] nums, long target, int left, int right){
if(left > right)
return -1;
int mid = (left + right) / 2;
if(nums[mid] > target)
return getIndex(nums, target, left, mid - 1);
else if (nums[mid] < target)
return getIndex(nums, target, mid + 1, right);
else
return mid;
}
}