leetcode (力扣) 18. 四數之和 (四指針)

題目在這：​​https://leetcode-cn.com/problems/4sum/​​

思路分析:

前兩天做了​​三數之和​​​，還有個​​最接近的三數之和​​。今天又來了個四數之和。明天五數之和？後天N數之和？

題目和三數之和的思路是一樣的，隻不過這次用了四個指針。

四個指針 k–>i–>f–>j 。

使用k指針循環周遊數組， 初始時 k在第一個 i在k後面一個 f在i後面一個 j在最後一個。

• 如果這四指針相加起來的值等于目标值，則 j往左挪動，f往右挪動。
• 如果小于，則說明需要加大，f往右挪動
• 如果大于，則說明需要減小，j往左挪動，
• 當 f<j 或者f =j時 退出本次循環，然後 i往後挪動一個位置，重置f和j的位置，繼續循環。
• 當 i < j-1時，退出本次循環，k将往後挪，此時重置i的值。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        print(nums)
        # 四個指針
        res  = []
        if len(nums) < 4:
            return res
        for k in range(len(nums)-3):
            i = k + 1
            j = len(nums)-1
            if k !=0 and nums[k] == nums[k-1]:
                continue
            while i < j-1:
                f = i + 1
                while f < j:
                    s = nums[k] + nums[i] + nums[f] + nums[j]
                    if s  == target:
                        res.append([nums[k] ,nums[i] ,nums[f] ,nums[j]])
                        f +=1
                        j -=1
                        while f < j and nums[f] == nums[f-1]:
                            f +=1
                        while f < j and nums[j] == nums[j+1]:
                            j -=1
                    elif s < target:
                        f +=1
                        while f < j and nums[f] == nums[f-1]:
                            f +=1
                    elif s > target:
                        j -=1
                        while f < j and nums[j] == nums[j+1]:
                            j -=1

                i +=1
                j = len(nums)-1
                while i < j-1 and nums[i] == nums[i-1]:
                    i +=1

        print(res)
        return