15. 三数之和LeetCode

• 这算是小总结吧，代码啥的大体上跟大家的一样，只不过我认为官方应该多一个保证不同的操作（反正是通过了，就姑且当我的想法对吧）（明明四数值和官方都进行了保证重复操作，而三个竟然没有都进行，我不理解。）
• 还是，找几个数的和等于某数，就一定会用到目标数-第一个=剩下两个数的和
• 为了不重复，需要进行排序
• 第二个数和第三个数的寻找可以通过使用双指针，一个从先往后，另一个当两数之和大于目标-第一个数的时候，从后往前进行寻找（因为总和一定，一个数大，另一个数必然减小），这样节省了一个循环呢！第三个数一定比第二个数大，否则也不会存在了！
• 不同中最经典的情况就是0,0,0,0,0了，这结果只能是000，而不从五个零中任意取出3个零，所以要保证，每次选取的数字都是不同的
• 严格意义上来说，这个保证每个元素不相同是在存入到输出的集合之后保证的或已经有一个数的前提下才行，如果一开始就保证，那么当0,0,0,0,0就一般是错误的解（类似的错误还有很多），所以first是大于0而不是从0开始，second也是从first+2开始，这些都是为了保证起码有一个数，不然可能就直接没了。
• 其实压入之前去重和压入之后去重都一样，只不过，压入之前去重需要保证至少有一个会压入（也就是不从头开始，从第二个开始）；而压入之后去重则没有这么多考虑，或者说，这其实与循环有关，本身用for进行循环的时候，用if搞去重，没有for之后就得自己想办法去重，自然形式也不一样，也就不用苛求用同一种方法进行去重

  • // 只是用first举个例子，其实是三个都需要保证取的下一个元素是不重复的

    if (first > 0 && nums[first] == nums[first - 1]) {

    continue;

    }

    if (second > first + 1 && nums[second] == nums[second - 1]) {

    continue;

    }

    

• 当第二个数与第三个数相等的时候，结束。

	import java.util.*;
	
	class Solution {
	    public List<List<Integer>> threeSum(int[] nums) {
	        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);
	                    while (second < third && nums[third] == nums[third - 1]) {
	                        third--;
	                    }
	                }
	            }
	        }
	        return ans;
	    }
	}

最后

以上就是合适荷花为你收集整理的15. 三数之和LeetCode的全部内容，希望文章能够帮你解决15. 三数之和LeetCode所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。