Leetcode面试经典150题-15.三数之和
解法都在代码里，不懂就留言或者私信
class Solution {/**每次做这个题都想着这事最后一次了，但是确实很高频，还是多练练吧基本思路：先把原来的数组按照从小到大的顺序排列，然后我们从头开始确定第一个数，然后从它后面的数里确定第二个数和第三个数寻找第二和第三个数使用双指针，left和right分别指向后面区间第一个和最后一个位置，如果后面两个数的和小于了第一个数的相反数则left右移，如果等于记录答案left和right同时移动，如果大于right左右，左移右移的过程中要注意如果当前数和上个尝试的数一样比如left和left-1，right和right+1，就直接跳过如果第一个数大于0了，停止，因为它后面的数都大于等于它，它都大于0了，后面不可能存在和它加一起等于0的两个数 */public List<List<Integer>> threeSum(int[] nums) {/**先定义结果list */List<List<Integer>> ans = new ArrayList<>();/**给数组排个序,默认按照从小到大排序*/Arrays.sort(nums);/**这里可以判断一下如果第一个数大于0，直接返回空的，但是也可以不用这样，遍历的过程中也可以判断这里注意firstNum的范围是<nums.length - 2,因为你总要给后面留两个数吧*/for(int firstNum = 0; firstNum <nums.length - 2; firstNum++) {if(nums[firstNum] > 0) {break;}/**如果当前数不是第一个数并且和上个数相等，直接忽略 */if(firstNum != 0 && nums[firstNum] == nums[firstNum - 1]) {continue;}int left = firstNum + 1;int right = nums.length - 1;int target = -nums[firstNum];/**这里一定要写小于，因为他们两个不能相等 */while(left < right) {if(nums[left] + nums[right] < target) {left ++;} else if(nums[left] + nums[right] > target) {right --;} else {/**如果left是我们考虑范围的第一个数字或者它和上个数不相等，收集答案如果不是第一个数并且和上个数相等，其实就是执行left++, right--为什么不判断right位置呢？ 因为left和right凑够了target这个和，如果left位置和left-1相等那right和right+1也必然相等，不管我们搜集不收集答案，都要执行left++, right--的操作所以提取到最后省略else的部分*/if(left == firstNum + 1 || nums[left] != nums[left-1]) {List<Integer> curList = new ArrayList<>();curList.add(nums[firstNum]);curList.add(nums[left]);curList.add(nums[right]);ans.add(curList);}left ++;right --;}}}return ans;}
}运行结果，不算特别满意，这应该是最优解了
