问题描述
https://leetcode.com/problems/4sum/
解决思路
基本和3Sum一致
代码
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums == null || nums.length < 4) return res;
for (int i = 0; i < nums.length - 3; i++) {
//if same, skip to next
if(i != 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length - 2; j++) {
if(j != i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = nums.length - 1;
while(left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if(sum == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);
res.add(list);
left = moveRight(left + 1, right, nums);
right = moveLeft(left, right - 1, nums);
}
if(sum < target) {
left = moveRight(left + 1, right, nums);
}
if(sum > target){
right = moveLeft(left, right - 1, nums);
}
}
}
}
return res;
}
public int moveRight(int left, int right, int[] nums){
while(left < right && nums[left] == nums[left - 1]){
left++;
}
return left;
}
public int moveLeft(int left, int right, int[] nums){
while(left < right && nums[right] == nums[right + 1]){
right--;
}
return right;
}
}
复杂度分析
- 时间复杂度：O(N^3)
- 空间复杂度：O(N^2)
