18. 四数之和 - Kotlin 双指针

原题地址：https://leetcode.cn/problems/4sum/description/

题解

在15. 三数之和的基础上加一层循环

不管是几数之和，都是先排序，嵌套N-2次循环，然后在最后两次循环通过双指针减少一层

• 对于每一次循环，都从上一级循环的下一个元素起始
• 对于每一次循环，若当前元素与上一个元素相同则跳过

双指针中

• 若sum<target则left++
• 若sum>target则right–
• 若sum=target则组合加入ans，然后循环left++和right–直至left指向下一个不同的数，right指向下一个不同的数或者left>=right

时间复杂度：O(N^3)

空间复杂度：O(1)

class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        val ans=ArrayList<List<Int>>()
        nums.sort()
        for(i in nums.indices){
            if(i>0&&nums[i]==nums[i-1])continue
            for (j in i+1 until nums.size){
                if(j>0&&j-1!=i&&nums[j]==nums[j-1])continue
                if(j==i)continue
                var left=j+1
                var right=nums.size-1
                var sum:Long
                while (left<right){
                    sum= nums[i].toLong()+nums[j].toLong()+nums[left].toLong()+nums[right].toLong()
                    if(sum<target||left==i||left==j){
                        left++
                    }else if(sum>target||right==i||right==j){
                        right--
                    }else{
                        ans.add(listOf(nums[i],nums[j],nums[left],nums[right]))
                        left++
                        while (left<right&&nums[left]==nums[left-1]){
                            left++
                        }
                        right--
                        while (left<right&&nums[right]==nums[right+1]){
                            right--
                        }
                    }
                }
            }
        }
        return ans
    }
}