Q33 LeetCode18 四数之和

1.与三数之和类似

2.定前两个数，后面使用双指针移动

3.注意10⁹需要用long接，int就超出界限了

4.while (left < right && nums[left] == nums[++left]); 一个循环去除重复

 1 class Solution {
 2   public List<List<Integer>> fourSum(int[] nums, int target) {
 3     if (nums == null || nums.length < 4)
 4         return new ArrayList<>();
 5 
 6     Arrays.sort(nums);
 7 
 8     List<List<Integer>> res = new ArrayList<>();
 9 
10     // O(n^3)
11     for (int i = 0; i < nums.length - 3; i++) {
12         // 忽略后面与前面重复的元素
13         if (i > 0 && nums[i] == nums[i - 1]) continue;
14 
15         for (int j = i + 1; j < nums.length - 2; j++) {
16             // 忽略后面与前面重复的元素
17             if (j > i + 1 && nums[j] == nums[j - 1]) continue;
18 
19             long partSum = nums[i] + nums[j];
20             int left = j + 1;
21             int right = nums.length - 1;
22             long remainder = (long)target - partSum;
23             
24             while (left < right) {
25                 int sum =nums[left] + nums[right];
26 
27                 if (sum > remainder) {
28                     right--;
29                 } else if (sum < remainder) {
30                     left++;
31                 } else {
32                     res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
33                     while (left < right && nums[left] == nums[++left]);
34                     while (left < right && nums[right] == nums[--right]);
35                 }
36             }
37         }
38     }
39 
40     return res;
41 }
42 
43 }