目录

• -----------------8.28-----------------------
• 16、最接近的三数之和
• 18.四数之和
• 209、长度最小的子数组
• 39、组合总和
• 40、组合总和II
• 287、寻找重复数

-----------------8.28-----------------------

16、最接近的三数之和

class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int n = nums.length;int best = 10000000;// 枚举 afor (int i = 0; i < n; ++i) {// 保证和上一次枚举的元素不相等if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 使用双指针枚举 b 和 cint j = i + 1, k = n - 1;while (j < k) {int sum = nums[i] + nums[j] + nums[k];// 如果和为 target 直接返回答案if (sum == target) {return target;}// 根据差值的绝对值来更新答案if (Math.abs(sum - target) < Math.abs(best - target)) {best = sum;}if (sum > target) {// 如果和大于 target，移动 c 对应的指针int k0 = k - 1;// 移动到下一个不相等的元素while (j < k0 && nums[k0] == nums[k]) {--k0;}k = k0;} else {// 如果和小于 target，移动 b 对应的指针int j0 = j + 1;// 移动到下一个不相等的元素while (j0 < k && nums[j0] == nums[j]) {++j0;}j = j0;}}}return best;}
}

18.四数之和

class Solution {public List<List<Integer>> fourSum(int[] nums,int target){/*定义一个返回值*/List<List<Integer>> result=new ArrayList<>();/*当数组为null或元素小于4个时，直接返回*/if(nums==null||nums.length<4){return result;}/*对数组进行从小到大排序*/Arrays.sort(nums);/*数组长度*/int length=nums.length;/*定义4个指针k，i，j，h  k从0开始遍历，i从k+1开始遍历，留下j和h，j指向i+1，h指向数组最大值*/for(int k=0;k<length-3;k++){/*当k的值与前面的值相等时忽略*/if(k>0&&nums[k]==nums[k-1]){continue;}/*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏*/int min1=nums[k]+nums[k+1]+nums[k+2]+nums[k+3];if(min1>target){break;}/*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/int max1=nums[k]+nums[length-1]+nums[length-2]+nums[length-3];if(max1<target){continue;}/*第二层循环i，初始值指向k+1*/for(int i=k+1;i<length-2;i++){/*当i的值与前面的值相等时忽略*/if(i>k+1&&nums[i]==nums[i-1]){continue;}/*定义指针j指向i+1*/int j=i+1;/*定义指针h指向数组末尾*/int h=length-1;/*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏*/int min=nums[k]+nums[i]+nums[j]+nums[j+1];if(min>target){break;}/*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/int max=nums[k]+nums[i]+nums[h]+nums[h-1];if(max<target){continue;}/*开始j指针和h指针的表演，计算当前和，如果等于目标值，j++并去重，h--并去重，当当前和大于目标值时h--，当当前和小于目标值时j++*/while (j<h){int curr=nums[k]+nums[i]+nums[j]+nums[h];if(curr==target){result.add(Arrays.asList(nums[k],nums[i],nums[j],nums[h]));j++;while(j<h&&nums[j]==nums[j-1]){j++;}h--;while(j<h&&i<h&&nums[h]==nums[h+1]){h--;}}else if(curr>target){h--;}else {j++;}}}}return result;}}

209、长度最小的子数组

class Solution {public int minSubArrayLen(int s, int[] nums) {int n = nums.length;if (n == 0) {return 0;}int ans = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {int sum = 0;for (int j = i; j < n; j++) {sum += nums[j];if (sum >= s) {ans = Math.min(ans, j - i + 1);break;}}}return ans == Integer.MAX_VALUE ? 0 : ans;}
}

39、组合总和

40、组合总和II

287、寻找重复数

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！