双指针
leetcode209】长度最小的子数组
public class MinSubArrayLen {
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int minlen = Integer.MAX_VALUE;
int start = 0;
int end = 0;
int sum = 0;
int length = nums.length;
while (end < length) {
sum += nums[end++];
while (sum >= s) {
minlen = (end - start) < minlen ? (end - start) : minlen;
sum -= nums[start++];
}
}
return minlen == Integer.MAX_VALUE ? 0 : minlen;
}
}
leetcode15. 三数之和
排序 加 双指针。在遍历的过程中注意减枝和去重
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 3) {
return result;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
//减枝
if (nums[i] > 0) {
break;
}
//去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int start = i + 1;
int end = nums.length - 1;
while (start < end) {
if (nums[start] + nums[end] + nums[i] < 0 || (start > i + 1 && nums[start] == nums[start - 1])) {
start++;
} else {
if (nums[start] + nums[end] + nums[i] > 0 || (end < nums.length - 1 && nums[end] == nums[end + 1])) {
end--;
} else {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[start++]);
list.add(nums[end--]);
result.add(list);
}
}
}
}
return result;
}
public int threeSumClosest(int[] nums, int target) {
assert nums.length > 2;
Arrays.sort(nums);
int left;
int right;
int sum3; //数组中的三个数的和
int res = 0; //记录返回结果
int tmp = Integer.MAX_VALUE; //记录sum3和target的差的绝对值
for (int i = 0; i < nums.length - 2; i++) {
left = i + 1;
right = nums.length - 1;
while (left < right) {
sum3 = nums[left] + nums[right] + nums[i];
//如果已经找到等于target的三个数,直接返回即可。
if(sum3 == target){
return target;
}
if (Math.abs(sum3 - target) < tmp) {
tmp = Math.abs(sum3 - target);
res = sum3;
}
if (sum3 > target) {
right--;
} else {
left++;
}
}
}
return res;
}