publicclassThreeSumBinarySearchimplementsThreeSum{ @Override publicintcount(int[] nums){ Arrays.sort(nums); int N = nums.length; int cnt = 0;
for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { int target = -nums[j] - nums[i]; int index = BinarySearch(nums,target); // 应该注意这里的下标必须大于j,否则会重复统计 if (index > j){ cnt++; } } } return cnt; }
publicintBinarySearch(int[] nums,int target){ int l = 0; int h = nums.length - 1; while (l <= h){ int m = l + (h-l)/2; if (target == nums[m]){ return m; } elseif (target >= nums[m]){ l = m + 1; } else{ h = m - 1; } } return -1; }
publicstaticvoidmain(String[] args){ ThreeSumBinarySearch binarySearch = new ThreeSumBinarySearch(); int[] a = {-1,1,0,3,5,8};
int count = binarySearch.count(a); System.out.println(count); }
publicclassThreeSumTwoPointerimplementsThreeSum{ @Override publicintcount(int[] nums){ int N = nums.length; int cnt = 0;
Arrays.sort(nums); for (int i = 0; i < N - 2; i++) { int l = i + 1; int h = N - 1; int target = -nums[i]; while (l < h){ int sum = nums[l] + nums[h]; if (sum == target){ cnt ++; l ++; h --; } elseif (sum < target){ l ++; }else { h --; } } } return cnt; } }