Leetcode題解 Python & C#：4Sum

如果有做出 3Sum 的人，這類題有一套公式，即使用 TwoPointer 的技巧，靠迴圈、加速搜遍數列。

3Sun是選定一個 i(由前往後)，4Sum就多選一個 j(由後往前)，剩下用 l、r，即 TwoPointer，用總和值來決定移動 l 還是 r。

先把數列排序，若 nums[i] + nums[l] + nums[r] + nums[j] > target，則我們要縮小總和，因此讓 r - 1，反則 l + 1，

這使得每次移動都讓總和與目標值靠近。如果跟總和跟目標值相同，記錄組合，然後移動 l 與 r 。  

由於不能重複，存放組合的資料型態可以選hash家族，這樣就能有效率的避免有同樣組合被計到二次以上。

又或者將重複的狀況跳過，不僅可加速迴圈，也可以直接用 list 放結果，不用轉換資料型態。 

Python(基本)

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        result = set()
        nums.sort()
        for i in range(n-3):
            for j in range(n-1,i+2,-1):
                l, r = i+1, j-1
                while l < r:
                    v = nums[i] + nums[l] + nums[r] + nums[j]
                    if v > target: 
                        r -= 1
                    elif v < target:
                        l += 1
                    else:                     
                        result.add((nums[i],nums[l],nums[r],nums[j]))
                        l += 1
                        r -= 1
        return result

C#

public class Solution {
    public IList> FourSum(int[] nums, int target) {
        Array.Sort(nums);
        int n = nums.Length;
        IList> result = new List>();
        for(int i = 0; i < n - 3; i++)
        {
            for(int j = n - 1; j > i + 2; j--)
            {
                var l = i + 1; var r = j - 1;
                while(l < r)
                {
                    var nsum = nums[i] + nums[l] + nums[r] + nums[j];
                    if(nsum == target)
                    {
                        result.Add(new List(){nums[i], nums[l], nums[r], nums[j]});
                        while(l < r && nums[l] == nums[l+1] && nums[r] == nums[r-1])
                        {
                            l++;
                            r--;
                        }
                        l += 1;
                        r -= 1;   
                    }
                    else if(nsum > target)
                    {
                        r -= 1;
                    } 
                    else
                    {
                        l += 1;
                    }
                }
                while(j > i + 2 && nums[j] == nums[j-1]){j--;}
            }
            while(i < n - 3  && nums[i] == nums[i+1]){i++;}
        }
        return result;
    }
}

不過會發現，Python這樣子的寫法不夠快，有沒有什麼可以加速的條件可用。

例如重複跳過，若接下來找不到目標值，則進入下一個迴圈。這些條件都很好理解，就不多敘述了。

在添加了一些提前中止的條件後，速度可以壓在100ms以內。

Python

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        result = []
        nums.sort()
        for i in range(n-3):
            if( i > 0 and nums[i] == nums[i-1]): continue
            if nums[i] * 4 > target: break
            for j in range(n-1,i+2,-1):
                if(j target: 
                        if curSum + 2 * nums[l] > target: break
                        r -= 1
                    elif v < target:
                        if curSum + 2 * nums[r] < target: break
                        l += 1
                    else:                     
                        result.append([nums[i],nums[l],nums[r],nums[j]])
                        while(l < r and nums[l] == nums[l+1] and nums[r] == nums[r-1]):
                            l += 1
                            r -= 1      
                        l += 1
                        r -= 1
        return result