NO.15 三数之和 中等
这道题有一个麻烦的地方,就是需要去重,如果直接简单的三重循环暴力破解的话,除了时间复杂度问题之外还不便于去重。
思路一:双指针法 1. 首先对数组进行排序。2. 依次遍历数组元素,每遍历一个元素nums[i]时,就用左右指针指向nums[i]后面元素部分的两端,即指向nums[L]和nums[R],判断nums[i]、nums[L]和nums[R]之和sum是否等于0,等于0则加入结果集。如果sum>0,则说明需要较小的数字,即”R–”。如果sum<0,则说明需要较大的数字,即”L++”。循环直至左右指针相遇,即后面元素部分已组合完毕,则本次循环结束。3. 如果遍历到某个元素nums[i]已经大于0,则三数之和必然大于0(充分利用排序后的特点,减少无用的比较),结束循环。
然后是该算法去重的思路:4. 如果nums[i]==nums[i-1],就会导致结果重复,所以应该跳过。5. 如果sum==0的时候,nums[L]==num[L+1]就会导致结果重复,所以应该跳过,L++。6. 如果sum==0的时候,nums[R]=nums[R-1]就会导致结果重复,所以应该跳过,R–。
1 | public List<List<Integer>> threeSum(int[] nums) { |
时间复杂度:O(n^2)
本人菜鸟,有错误请告知,感激不尽!