2023-11-09
思路:
此题并不适合哈希表法,去重问题很麻烦
用双指针法,但是注意:双指针法如果不优化(也就是3层暴力)是超时的
class Solution { public List<List<Integer>> threeSum(int[] nums) { //三者都不相同,和为0 //可以作为i》j》k 不影响的 //可能有多个 //暴力法 3层循环,有点bt //借用哈希表,变为2层循环 //会有去重问题 //可以进一步思考-》nums[i]<=nums[j]<=nums[k] //进一步思考-》可以先将数组就行排序 //还是有去重问题,此题不适合哈希表法,适合双指针 List<List<Integer>> res=new ArrayList<>(); Arrays.sort(nums); for(int i=0;i<nums.length;){ for(int j=i+1;j<nums.length;){ for(int k=j+1;k<nums.length;){ if(nums[i]+nums[j]+nums[k]==0){ List<Integer> l=new ArrayList<>(); l.add(nums[i]); l.add(nums[j]); l.add(nums[k]); res.add(l); } int z=nums[k]; k++; while(k<nums.length && nums[k]==z){ k++; } } int y=nums[j]; j++; while(j<nums.length && nums[j]==y){ j++; } } int x=nums[i]; i++; while(i<nums.length && nums[i]==x){ i++; } } return res; } }
下面是双指针优化内层的2个循环,使得o(n3)变为o(n2)
若和大于 0,说明 nums[R]nums[R]nums[R] 太大,R 左移
若和小于 0,说明 nums[L]nums[L]nums[L] 太小,L 右移
class Solution { public List<List<Integer>> threeSum(int[] nums) { //三者都不相同,和为0 //可以作为i》j》k 不影响的 //可能有多个 //暴力法 3层循环,有点bt //借用哈希表,变为2层循环 //会有去重问题 //可以进一步思考-》nums[i]<=nums[j]<=nums[k] //进一步思考-》可以先将数组就行排序 //还是有去重问题,此题不适合哈希表法,适合双指针 int n = nums.length; Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<List<Integer>>(); // 枚举 a for (int first = 0; first < n; ++first) { // 需要和上一次枚举的数不相同 if (first > 0 && nums[first] == nums[first - 1]) { continue; } // c 对应的指针初始指向数组的最右端 int third = n - 1; int target = -nums[first]; // 枚举 b for (int second = first + 1; second < n; ++second) { // 需要和上一次枚举的数不相同 if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } // 需要保证 b 的指针在 c 的指针的左侧 while (second < third && nums[second] + nums[third] > target) { --third; } // 如果指针重合,随着 b 后续的增加 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环 if (second == third) { break; } if (nums[second] + nums[third] == target) { List<Integer> list = new ArrayList<Integer>(); list.add(nums[first]); list.add(nums[second]); list.add(nums[third]); ans.add(list); } } } return ans; } }