15.三数之和

链接

思路

排序+双指针
1.对元素从小达到排序
2.固定i，开始循环
3.循环开始，判断i-1是否和前面的i相同，如果相同，就跳过。i-1是为了避免索引溢出
4.计算三数之和，如果等于0，那就加入结果；并且j和k都移动一位，然后判断是否和下一个相同，相同就跳过
5.如果小于0，说明j太小，右移一位
6.如果大于0，说明k太大，左移一位

代码

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:res = []nums.sort()n = len(nums)for i in range(n):if i > 0 and nums[i] == nums[i-1]:continuej,k = i+1,n-1while j < k:temp = nums[i] + nums[j] + nums[k]if temp == 0:res.append([nums[i], nums[j], nums[k]])j,k = j+1,k-1while j < k and nums[j] == nums[j-1]:j = j+1while j < k and nums[k] == nums[k+1]:k -= 1elif temp < 0:j = j+1else:k = k-1return res

复杂度

O(N^2)
外层for循环O(N)，内存while循环O(N)