四數之和(18)

題目要求

給你一個由 n 個整數組成的數組 nums ，和一個目標值 target 。請你找出並返回滿足下述全部條件且不重覆的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個四元組元素一一對應，則認為兩個四元組重覆）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意順序 返回答案 。

這道題整體還是和三數之和的解法相似，只不過這現在是需要兩層for迴圈了，有加了一個j作為內迴圈，內層迴圈裡面還是採用雙指針法：首先我們要對數組進行排序,我們開始遍曆數組從0下標開始記為i，定義left指針為i+1,right指針為nums.length-1(最後一位),然後開始收集結果，如果我們的nums[i]+nums[left]+nums[right]<0則left指針右移一位,如果我們的nums[i]+num[j]+nums[left]+nums[right]>0則right指針左移一位，如果等於0則加入結果集中，但是這裡有很多去重的細節，我們看以下代碼中的解法。(在內層迴圈那個剪枝操作那裡我們不能像第一層for迴圈那樣直接返回result,因為可能第二層for迴圈裡面還有我們想要的結果，你可以寫為continue或者你直接不寫也是一樣的),這裡真是個天坑，因為這裡的i和j不是一直都是緊挨著的，它倆指針會越來越遠的，這裡需要註意一下

import java.util.*;
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length < 4) {
            return result;
        }
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 3; i++) {

            if(nums[i]>0 && nums[i]>target){
                return result;
            }
            
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            for (int j = i + 1; j < nums.length - 2; j++) {

                //這個地方真是個天坑，本人為此耗時倆個小時
                if (nums[i]+nums[j] > 0 && nums[i]+nums[j] > target) {
                    continue;
                }
                
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                
                int left = j + 1;
                int right = nums.length - 1;
                
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        
                        // 跳過重覆的元素
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        
        return result;
    }
}