做算法题的时候，几乎不可避免要跟数组打交道。在LintCode上数组那一章有这么一些题目：
1）547. Intersection of Two Arrays
比较简单。要求找到2个数组的交集，简单点的方法就是用2个hashSet，第一个HashSet存第一个数组的元素。然后扫描第二个数组，如果第二个数组中的元素在第一个HashSet中出现了，那么就把它加到第二个HashSet中。最后第二个HashSet就是两个数组的交集了。
要求在一个数组中找到一个子数组，使得这个子数组的和为0。就是比如一个数组是[12, -3, 1, 2, -3, 4] ，[-3, 1, 2] 这一段的和是0。这道题有个技巧，我用sum函数代表前面n个元素的和.
sum(1) = 12
sum(2) = 9
sum(3) = 10
sum(4) = 12
发现规律木有？那就是sum(1) 等于 sum(4) ，而第1+1个元素到第4个元素的字数组和恰好就为0。
所以方法就是求连续子数组的和，然后看哪两个sum相等，相等的下标区间就是答案了。代码如下：
public ArrayList<Integer> subarraySum(int[] nums) {
ArrayList<Integer> res = new ArrayList<Integer>();
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0, -1);
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum)) {
res.add(map.get(sum) + 1);
res.add(i);
break;
}
map.put(sum, i);
}
return res;
}比较简单。对2个有序数组A和B进行合并，要求把B合并进A，因为A数组尾部有足够的空间可以容纳B。建议从后往前扫描，这样的代码更加简洁。扫描完了后看B数组有没有剩余，若有剩余则把剩余的元素也添加到A数组头部。代码如下：
public void mergeSortedArray(int[] A, int m, int[] B, int n) {
while (m >= 1 && n >= 1) {
if (A[m - 1] >= B[n - 1]) {
A[m + n - 1] = A[m - 1];
m--;
} else {
A[m + n - 1] = B[n - 1];
n--;
}
}
while (n > 0) {
A[m + n - 1] = B[n - 1];
n--;
}
return;
}要求最大的连续子数组之和。Given the array [?2,2,?3,4,?1,2,1,?5,3], the contiguous subarray [4,?1,2,1] has the largest sum = 6
可以用贪心算法解决。
sum用于记录当前的子数组的和，如果当前位置之前的子数组和sum小于0，那么这个sum加上当前的nums[i]肯定会比nums[i]自己要小，所以此时我就把sum清零，从当前位置开始记录子数组和。代码如下：
public int maxSubArray(int[] nums) {
// greedy algorithm
// sum用于记录当前的字数组的和，如果当前位置之前的子数组和sum小于0
// 那么这个sum加上当前的nums[i]肯定会比nums[i]自己要小，所以此时我就把sum清零，从当前位置开始记录子数组和
int sum = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (sum < 0) {
sum = 0;
}
sum += nums[i];
max = Math.max(sum, max);
}
return max;
}要求在数组中找到2个数，使得这两个数之和最接近给定的target。Given array nums = [-1, 2, 1, -4], and target = 4. The minimum difference is 1. (4 - (2 + 1) = 1).
一开始我用的是2层循环，暴力的对数组中每两个数求和。不过后来在youtube上看到了geeksforgeeks的一个老印的解法，是O(nlog)的。第一遍就排序。然后再设置2个指针，分别从两边往中间扫描。2个指针所对应的数之和如果大于target，那么就把右指针往左边移动；反之则把左指针往右边移动。这样能够保证找到最接近于target的两数之和。（具体怎么证明我还没想清楚，但这个思路绝对是对的，求大神给个清晰地数学证明）。
算法流程如下：
1) Sort all the elements of the array.
2) Keep 2 index variables for left and right index.
3) Initialize: left index l = 0. r = n-1.
4) sum = a[l]+a[r]
5) If sum is negative than l++ else r — .
6) Keep track of absolute min sum.
7) Repeat steps 4,5,6 until l < r
代码如下：
public int twoSumCloset(int[] nums, int target) {
Arrays.sort(nums);
int left = 0, right = nums.length - 1;
int min = Integer.MAX_VALUE;
while (left < right) {
int sum = nums[left] + nums[right];
int diff = Math.abs(sum - target);
min = Math.min(min, diff);
if (sum > target) {
right--;
} else {
left++;
}
}
return min;
}数组中的元素只有0、1、2这三个类型的数字，要求对他排序。Given [1, 0, 1, 2], sort it in-place to [0, 1, 1, 2]。官网提示了一种naive的做法：A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0‘s, 1‘s, and 2‘s, then overwrite array with total number of 0‘s, then 1‘s and followed by 2‘s. Could you come up with an one-pass algorithm using only constant space?
但是得循环2次，有没有办法只用一次循环搞定呢？那就得用双指针法了。
从数组两端向中间遍历，前面放0，后面放2。把前面出现的2放到后面，后面出现的0放到前面，这样中间剩下的就是1
我的解法是定义指针start = 0，指针end = n - 1；一次遍历，如果遇到0，交换给start，遇到2，交换给end，遇到1别管。代码如下：
public void sortColors(int[] nums) {
int start = 0, end = nums.length - 1;
int index = 0;
while (index <= end) {
if (nums[index] == 0) {
swap(nums, index, start);
index++;
start++;
} else if (nums[index] == 1) {
index++;
} else {
swap(nums, index, end);
end--;
}
}
}
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
算法的关键在于，当从前往后扫描数组的时候，把0往最左边放，把2往最右边放。
当index对应的元素是0时，就把它和start交换，往前面放。因为是从左往右扫描的，所以每次遇到0都往左边放，这样能够保证左边都是0。
当index对应的元素是1时，直接继续扫描，不用管它。（因为在之后的扫描会把这个1变为0或者维持1不变）
当index对应的元素是2时，我们把它与end交换后，只需要把end指针往左边挪一位，而不用给index++。但是当index对应的元素是0时，我们却要给index++。这是为啥呢。
原因在于，index对应的值为2时，end对应的值也可能为2，在这种情况下，交换完了之后，index自己还是2，所以不行，index还的继续留在这个位置；
给定一个数组，要求找到他的子数组，使得子数组之和最接近于0。
做法就是利用前缀和，先用一个数组sum[i]来保存从nums[0]到nums[i]的和，同时还要记录下标。那么，我们想要得到nums[i]到nums[j]的和，只要用sum[j] - sum[i-1]就可以了。剩下的工作就是对sum数组排序，找到排序后相邻的差的绝对值最小的那一对节点。
class Pair {
int sum;
int index;
public Pair(int s, int i) {
sum = s;
index = i;
}
}
public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number
* and the index of the last number
*/
public int[] subarraySumClosest(int[] nums) {
int[] res = new int[2];
if (nums == null || nums.length == 0) {
return res;
}
int len = nums.length;
if(len == 1) {
res[0] = res[1] = 0;
return res;
}
Pair[] sums = new Pair[len+1];
int prev = 0;
sums[0] = new Pair(0, 0);
for (int i = 1; i <= len; i++) {
sums[i] = new Pair(prev + nums[i-1], i);
prev = sums[i].sum;
}
Arrays.sort(sums, new Comparator<Pair>() {
public int compare(Pair a, Pair b) {
return a.sum - b.sum;
}
});
int ans = Integer.MAX_VALUE;
for (int i = 1; i <= len; i++) {
if (ans > sums[i].sum - sums[i-1].sum) {
ans = sums[i].sum - sums[i-1].sum;
int[] temp = new int[]{sums[i].index - 1, sums[i - 1].index - 1};
Arrays.sort(temp);
res[0] = temp[0] + 1;
res[1] = temp[1];
}
}
return res;
}
}给定一个target，要求在数组中找到两个数之和等于target，并返回这两个数的下标。最简单的是2层循环嵌套暴力求解O(n^2)，稍微好一点的解法是先排序，然后再在排好序的数组中从两边往中间扫描，如果找到2个数之和等于target，就在原数组中扫描找到它们原来的下标并返回，不过时间复杂度好像也是O(n^2)，代码如下：
public int[] twoSum(int[] nums, int target) {
int[] res = new int[]{-1, -1};
int[] sorted = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
sorted[i] = nums[i];
}
Arrays.sort(sorted);
int left = 0, right = sorted.length - 1;
while (left < right) {
int sum = sorted[left] + sorted[right];
if (sum == target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == sorted[left] && res[0] == -1) {
res[0] = i + 1;
} else if (nums[i] == sorted[right] && res[1] == -1) {
res[1] = i + 1;
}
if (res[0] != -1 && res[1] != -1) {
if (res[0] > res[1]) {
int tmp = res[0];
res[0] = res[1];
res[1] = tmp;
}
return res;
}
}
} else if (sum > target) {
right--;
} else {
left++;
}
}
return res;
}有没有O(n)的解法呢？有的，那就是利用HashMap，如下所示：
我的目标是要找到a+b=target中的a和b，从左往右扫描数组，每次都把target-a加进map中，同时每次都在map中寻找看target-a存不存在：
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (map.get(nums[i]) != null) {
res[0] = map.get(nums[i]) + 1;
res[1] = i + 1;
}
map.put(target - nums[i], i);
}
return res;
}如果左指针对应的数≥k并且右指针对应的数＜k的话，那就交换（这是满足交换的情况）
不满足交换的情况的话，那我们就继续往中间移动左右指针
public int partitionArray(int[] nums, int k) {
int start = 0, end = nums.length - 1;
while (start < end) {
if (nums[start] >= k && nums[end] < k) {
swap(nums, start, end);
}
if (nums[end] >= k) {
end--;
}
if (nums[start] < k) {
start++;
}
}
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < k) {
count++;
}
}
return count;
}
private void swap(int[] nums, int a, int b) {
int tmp = nums[a];
nums[a] = nums[b];
nums[b] = tmp;
}要求找到2个有序数组的中数，比如Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5. Given A=[1,2,3] and B=[4,5], the median is 3.
一种直观的思路就是新开一个数组，把两个有序数组进行合并，然后再在新开的数组里面找到中数。代码如下：
public double findMedianSortedArrays(int[] A, int[] B) {
// write your code here
int m = A.length;
int n = B.length;
int[] all = new int[m + n];
while (m - 1 >= 0 && n - 1 >= 0) {
if (A[m - 1] > B[n - 1]) {
all[m + n - 1] = A[m - 1];
m--;
} else {
all[m + n - 1] = B[n - 1];
n--;
}
}
while (m - 1 >= 0) {
all[m + n - 1] = A[m - 1];
m--;
}
while (n - 1 >= 0) {
all[m + n - 1] = B[n - 1];
n--;
}
int len = all.length;
if (len % 2 == 1) {
return (double)all[len / 2];
} else {
return (all[len / 2] + all[len / 2 - 1]) / 2.0;
}
}这样的时间复杂度是O(m + n)，好像题目要求要O(log(m + n))的解法，应该是用二分法才能做到log级别。
这道题和4）41. Maximum Subarray 遥相呼应，求最小的连续子数组之和。如果前面的子数组sum比0大，那就从当前位置开始重新计算子数组之和，两个变量：sum代表局部的最小值、min是全局最小值。
public int minSubArray(ArrayList<Integer> nums) {
int sum = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.size(); i++) {
if (sum > 0) {
sum = 0;
}
sum += nums.get(i);
min = Math.min(sum, min);
}
return min;
}比较简单。对两个数组进行merge，新开一个数组，从后往前扫描。两两比较，较大的加到尾部。最后如果2个数组有剩余，则把剩余的元素也加进去。
原文：http://blog.csdn.net/luoshengkim/article/details/51570815