重建数组（高频）
LeetCode283.移动零
双指针，记录已经处理好的序列的尾部
class Solution {
public void moveZeroes(int[] nums) {
int k = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
swap(nums, i, k);
k++;
}
}
}
private void swap(int[] nums, int i, int k) {
int tmp = nums[i];
nums[i] = nums[k];
nums[k] = tmp;
}
}
Leetcode26. 删除有序数组中的重复项
思路是一样的，序列中是不重复的有序序列。
class Solution {
public int removeDuplicates(int[] nums) {
int k = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[k - 1]) {
swap(nums, i, k);
k++;
}
}
return k;
}
private void swap(int[] nums, int i, int k) {
int tmp = nums[i];
nums[i] = nums[k];
nums[k] = tmp;
}
}
双指针
剑指offer21.调整数组顺序使奇数位于偶数前面
一个指针向后，一个指针从尾部向前。i之前的元素都是奇数，j之后的元素都是偶数。
class Solution {
public int[] trainingPlan(int[] actions) {
int length = actions.length;
int i = 0, j = length - 1;
while (i < j) {
while (i < j && actions[i] % 2 != 0) {
i++;
}
while (i < j && actions[j] % 2 == 0) {
j--;
}
swap(actions, i, j);
}
return actions;
}
private void swap(int[] actions, int i, int j) {
int tmp = actions[i];
actions[i] = actions[j];
actions[j] = tmp;
}
}
LeetCode11. 盛最多水的容器
使用双指针。更高的一方不动，调整矮的一方，使得整体的高度在上升。
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1;
int res = 0;
while (i < j) {
if (height[i] < height[j]) {
res = Math.max(res, height[i] * (j - i));
i++;
} else {
res = Math.max(res, height[j] * (j - i));
j--;
}
}
return res;
}
}
LeetCode1.两数之和
不能重复使用当下元素，有一个测试用例是这样的
[3,2,4],6，由于索引为3的元素重复使用可以得到结果6.
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int[] res = new int[2];
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
Integer index = map.get(target - nums[i]);
res[0] = i;
res[1] = index;
break;
}
map.put(nums[i], i);
}
return res;
}
}
LeetCode167. 两数之和 II - 输入有序数组
class Solution {
public int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
int[] res = new int[2];
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else {
res[0] = i + 1;
res[1] = j + 1;
break;
}
}
return res;
}
}
