18.四數(shù)之和

題目鏈接：https://leetcode-cn.com/problems/4sum/

難度：中等

給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums 和一個(gè)目標(biāo)值 target爬骤，判斷 nums 中是否存在四個(gè)元素 a履怯，b氮帐，c 和 d 导俘，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復(fù)的四元組。

注意：

答案中不可以包含重復(fù)的四元組。

示例：

給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0例朱。

滿足要求的四元組集合為：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解法一：雙指針法 + 排序

解法思路：

若是做過15. 三數(shù)之和會(huì)發(fā)現(xiàn)這兩個(gè)題是一個(gè)解題思路。

我們利用一個(gè)雙重循環(huán)a和b來控制四個(gè)數(shù)中最小的兩數(shù)鱼蝉，再用雙指針l和r來控制另外兩數(shù)洒嗤。

計(jì)算：sum = nums[a]+nums[b]+nums[l]+nums[r];

若sum == target，則把這四個(gè)數(shù)添加到結(jié)果數(shù)組中

若sum > target魁亦，則說明r太大了渔隶，將r--，將指針r向左移動(dòng)洁奈。

若sum < target间唉，則說明l太大了，將l++利术，將指針l向右移動(dòng)呈野。

解決重復(fù)結(jié)果問題：

我們在四層變量值改變的時(shí)候，可以判斷一下印叁，是否和上一次的值相等被冒，若相等，直接跳過這次循環(huán)轮蜕。

時(shí)間復(fù)雜度優(yōu)化：

我們在外兩層a和b變量值改變的時(shí)候昨悼，可以計(jì)算一下，他們的最大值和最小值肠虽，若最大值比target還小幔戏，或者最小值比target還大，都可以直接跳過税课。

image.png

代碼:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        int l,r;
        int sum;
        int max,min;
        Arrays.sort(nums);
        int len = nums.length;
        
        for(int a = 0;a<len-3;a++) {
            //當(dāng)nums[a] == nums[a-1] 直接跳過
            if(a>0 && nums[a] == nums[a-1]) {
                continue;
            }
            
            //獲取當(dāng)前的最大值闲延，如果最大值比目標(biāo)值還小，直接跳過
            max = nums[a]+nums[len-3]+nums[len-2]+nums[len-1];
            if(max<target) {
                continue;
            }
            
            //獲取當(dāng)前的最小值韩玩，如果最小值比目標(biāo)值還大垒玲，直接跳過
            min = nums[a]+nums[a+1]+nums[a+2]+nums[a+3];
            if(min>target) {
                continue;
            }
            
            for(int b = a+1;b<len-2;b++) {
                //當(dāng)nums[b] == nums[b-1]直接跳過
                if(b>a+1 && nums[b] == nums[b-1]) {
                    continue;
                }
                l = b+1;
                r = len-1;
                
                //獲取當(dāng)前的最大值，如果最大值比目標(biāo)值還小找颓，直接跳過
                max = nums[a]+nums[b]+nums[r-1]+nums[r];
                if(max<target) {
                    continue;
                }
                
                //獲取當(dāng)前的最小值合愈，如果最小值比目標(biāo)值還大，直接跳過
                min = nums[a]+nums[b]+nums[l]+nums[l+1];
                if(min>target) {
                    continue;
                }
                
                while(l<r) {
                    sum = nums[a]+nums[b]+nums[l]+nums[r];
                    if(sum == target) {
                        results.add(Arrays.asList(nums[a],nums[b],nums[l],nums[r]));
                        l++;
                        r--;
                        
                        //當(dāng)nums[r]==nums[r+1]直接跳過
                        while(r<len-1 && r>l && nums[r]==nums[r+1]) {
                            r--;
                        }
                        //當(dāng)nums[l]==nums[l-1]直接跳過
                        while(l>b+1 && r>l && nums[l]==nums[l-1]) {
                            l++;
                        }
                    }else if(sum > target) {
                        r--;
                    }else {
                        l++;
                    }
                }
            }
        }
        return results;
    }
}