Day 16
题目描述（值得二刷）
思路
这里就不介绍暴力做法了（因为我试了一上午都超时了）
双指针做法
此题的难点有两个：1 时间复杂度 2 如何去重
做法如下：
- 对数组进行排序（这步很重要，因为我们的做法是先确定一个元素，往后找其余的元素，有序的话，假如出现-（1 -1 -1，0，1）这种情况，其实就可以规避掉后面两个-1的多余计算量）
- 从前向后遍历数组，如果出现重复元素就跳过，没有重复，设定该元素为第一个元素，将数组最后一个元素作为第三个元素，序号为last。（原因在于已经排序过了，最后一个元素是最大的），利用0-第一个元素得到剩余两个元素的和target。
- 从i+1向后遍历找第二个元素，同样的判断其是否重复，重复就跳过，不重复，设定为第二个元素，判断其是否在第三个元素左边并且相加后与target的关系
- while循环两者和大于target并且第二个元素在第三个元素左边，那么第三个元素向前移动（因为初始设置为他是最大的）
- 跳出循环存在三种情况：
- 第二个元素到第三个元素右边了，直接break，（这种情况说明就目前第一个元素而言，不可能找到等于0的情况，直接第一个元素更换。因为这种情况以及把第一个元素后的所有情况都尝试了一遍）
- 第二个元素最后加上第三元素小于target，说明这不是我们要找的，接着找下一个第二个元素。
- 如果等于target，就加入列表。
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list = new ArrayList<>();//结果列表Arrays.sort(nums);//排序for (int i = 0; i < nums.length; i++) {if(i>0&&nums[i]==nums[i-1]){//重复则下一个continue;}int last=nums.length-1;//设定第三个元素的序号int target = 0-nums[i];//设置剩下两个元素的和的目标值for (int j = i+1; j < nums.length; j++) {//找第二个元素if(j>i+1&&nums[j]==nums[j-1]){//重复则下一个continue;}while (j<last && nums[j]+nums[last]>target) {//修改第三个元素的值last--;}if(j==last){//说明第一个元素不对break;}if(nums[j]+nums[last]==target){//入队ArrayList<Integer> lis = new ArrayList<>();lis.add(nums[i]);lis.add(nums[j]);lis.add(nums[last]);list.add(lis);}}}return list;}
}
题目描述
思路
注意审题：总和大于等于target的 最短连续子数组
做法如下（滑动窗口）：
- start标记起始元素，len为结果，sum存放总和
- 向后遍历数组，sum不断获取总和，
- 如果sum比target大或者等于，即满足了条件，记录当前start与当前元素的距离，存放较小值到len中。
- 然后将sum值减去起始元素值，将起始元素向前移动。
class Solution {public int minSubArrayLen(int target, int[] nums) {int start,end,sum,len,min;start=0;//起始元素序号len=0;//结果min=99;sum=0;//总和for(int i=start;i<nums.length;i++){//可以将i定义为窗口的最后一个元素sum+=nums[i];while(sum>=target){//满足条件min=i-start+1;if(len==0||len>min){len=min;}sum=sum-nums[start];start++;//将起始元素向前移动，如果不满足target了//窗口最后一个元素也会向前移动，这样做就能找到所有满足条件的子序列}}return len;}
}