leetcode-三数之和

视频：https://www.bilibili.com/video/BV1bP411c7oJ/?spm_id_from=333.788&vd_source=dd84879fcf1be72f360461b01ecab0d6

从两数之和开始，排序后的两数之和，利用好升序的性质，可以将时间复杂度从on2降到on;

class Solution {public int[] twoSum(int[] numbers, int target) {//暴力没有利用好数组已经排好序的特性int i=0,j=numbers.length-1;while(i<j){//优化后 最小+最大 花了o1时间得到onint sum=numbers[i]+numbers[j]; //相加if(sum==target){return new int[]{i+1,j+1}; //直到找到答案}else if(sum<target){//小于 i++；i++;}else{//大于J--;j--;}}return null;}
}

//首先个数组排序 三数之和本质和两数之和是一样的；

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);//i j kint n = nums.length;int j = 0;int k = 0;List<List<Integer>> ans = new ArrayList<>();if (n == 3) {if (nums[0] + nums[1] + nums[2] == 0) {List<Integer> list = new ArrayList<Integer>();list.add(nums[0]);list.add(nums[1]);list.add(nums[2]);ans.add(list);}}for (int i = 0; i < n - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {//如果现在都大于0了 直接break;break;}j = i + 1; k = n - 1;while (j < k) {int s = nums[i] + nums[j] + nums[k]; //三个数字之和if (s > 0) {k = k - 1;} else if (s < 0) {j = j + 1;} else {List<Integer> list = new ArrayList<Integer>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);ans.add(list); //找到一个符合的//因为是不能重复的,所以此时还需要移动 j和k的值j += 1; while (j < k && nums[j] == nums[j - 1]) j++;k -= 1;while (j < k && nums[k] == nums[k + 1]) k--;}}}return ans;}
}