1.两数之和II
只是简单使用使用双指针即可，设置两个指针 i 和 j 分别指向最左侧和最右侧的数字，它俩指向的数字和与 target 相比，如果小于 target就i++向右找，大于target就j– 向左找，只要等于 target 就找到了。
package com.dreams.leetcode;
import java.util.Arrays;
/**
* 2数之和
*/
public class Leetcode167 {
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));
}
static public int[] twoSum(int[] numbers, int target) {
int i = 0;
int j = numbers.length - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else {
break;
}
}
return new int[]{i + 1, j + 1};
}
}
2.三数之和
这里就是先固定一个数，再递归使用两数之和的方法。
代码：
package com.dreams.leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* 3数之和
*/
public class Leetcode15 {
static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new LinkedList<>();
dfs(3, 0, nums.length - 1, 0, nums,
new LinkedList<>(), result);
return result;
}
static void dfs(int n, int i, int j, int target, int[] nums,
LinkedList<Integer> stack,
List<List<Integer>> result) {
if (n == 2) {
// 套用两数之和求解
twoSum(i, j, nums, target, stack, result);
return;
}
for (int k = i; k < j; k++) {
// 检查重复
if (k > i && nums[k] == nums[k - 1]) {
continue;
}
// 固定一个数字，再尝试 n-1 数字之和
stack.push(nums[k]);
dfs(n - 1, k + 1, j, target - nums[k], nums, stack, result);
stack.pop();
}
}
public void twoSum(int i, int j, int[] numbers, int target,
LinkedList<Integer> stack,
List<List<Integer>> result) {
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else { // 找到解
ArrayList<Integer> list = new ArrayList<>(stack);
list.add(numbers[i]);
list.add(numbers[j]);
result.add(list);
// 继续查找其它的解
i++;
j--;
while (i < j && numbers[i] == numbers[i - 1]) {
i++;
}
while (i < j && numbers[j] == numbers[j + 1]) {
j--;
}
}
}
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
int[] candidates = {-4, -1, -1, 0, 0, 1, 1, 2};
System.out.println(threeSum(candidates));
}
}
3.四数之和
代码：
package com.dreams.leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* 4数之和
*/
public class Leetcode18 {
static List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new LinkedList<>();
dfs(4, 0, nums.length - 1, target, nums,
new LinkedList<>(), result);
return result;
}
static void dfs(int n, int i, int j, int target, int[] nums,
LinkedList<Integer> stack,
List<List<Integer>> result) {
if (n == 2) {
// 套用两数之和求解
twoSum(i, j, nums, target, stack, result);
return;
}
for (int k = i; k < j - (n - 2); k++) { // 四数之和 i <j-2 三数之和 i <j-1
// 检查重复
if (k > i && nums[k] == nums[k - 1]) {
continue;
}
// 固定一个数字，再尝试 n-1 数字之和
stack.push(nums[k]);
dfs(n - 1, k + 1, j, target - nums[k], nums, stack, result);
stack.pop();
}
}
static public void twoSum(int i, int j, int[] numbers, int target,
LinkedList<Integer> stack,
List<List<Integer>> result) {
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else { // 找到解
ArrayList<Integer> list = new ArrayList<>(stack);
list.add(numbers[i]);
list.add(numbers[j]);
result.add(list);
// 继续查找其它的解
i++;
j--;
while (i < j && numbers[i] == numbers[i - 1]) {
i++;
}
while (i < j && numbers[j] == numbers[j + 1]) {
j--;
}
}
}
}
public static void main(String[] args) {
System.out.println(fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
}
}利扣解：
package com.dreams.leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 4) {
return quadruplets;
}
Arrays.sort(nums);
int length = nums.length;
for (int i = 0; i < length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
for (int j = i + 1; j < length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
int left = j + 1, right = length - 1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
left++;
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return quadruplets;
}
}
4.盛最多水的容器
同样使用双指针
package com.dreams.leetcode;
/**
* 盛最多水的容器
*/
public class Leetcode11 {
static int maxArea(int[] height) {
int i = 0;
int j = height.length - 1;
int max = 0;
while (i < j) {
if (height[i] < height[j]) {
int area = (j - i) * height[i];
max = Math.max(max, area);
i++;
} else {
int area = (j - i) * height[j];
max = Math.max(max, area);
j--;
}
}
return max;
}
public static void main(String[] args) {
System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
}
}
参考
