1.move-zeroes（移动零）
给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序。必须在原数组上操作，同时最小化操作数。
public class Solution { /** * @param nums an integer array * @return nothing, do this in-place */ public void moveZeroes(int[] nums) { // Write your code here int zeroIndex = 0; int noZeroIndex = 0; int n = nums.length; while (zeroIndex < n && noZeroIndex < n) { while (zeroIndex < n && nums[zeroIndex] != 0) { zeroIndex++; } while (noZeroIndex < n && (nums[noZeroIndex] == 0 || noZeroIndex < zeroIndex)) { noZeroIndex++; } if (zeroIndex < n && noZeroIndex < n) { nums[zeroIndex++] = nums[noZeroIndex]; nums[noZeroIndex++] = 0; } } } }
注意：使用同向双指针zeroIndex和noZeroIndex记录0所在的位置和非0所在的位置。
若nums[zeroIndex]!=0,zeroIndex++;若nums[noZeroIndex]==0||noZeroIndex<zeroIndex（非0元素在0前面无需变动）,noZeroIndex++。然后交换两个位置上的数。
2.remove-duplicate-numbers-in-array（去除重复元素）
给一个整数数组，去除重复的元素，不需要保持原数组的顺序。你应该做：1.在原数组上操作2.将去除重复之后的元素放在数组的开头3.返回去除重复元素之后的元素个数。
时间复杂度和空间复杂度都为o(n)的解法:
public class Solution { /** * @param nums an array of integers * @return the number of unique integers */ public int deduplication(int[] nums) { // Write your code here HashSet<Integer> resultSet = new HashSet<Integer>(); for (int i = 0; i < nums.length; i++) { resultSet.add(nums[i]); } int length = resultSet.size(); int i = 0; for (Integer num : resultSet) { nums[i++] = num; } return length; } }
注意：HashSet集合中不允许有重复值。
时间复杂度为o(nlogn),o(1)额外空间的解法:
public class Solution { /** * @param nums an array of integers * @return the number of unique integers */ public int deduplication(int[] nums) { // Write your code here if (nums == null || nums.length == 0) { return 0; } Arrays.sort(nums); int len = 0; for (int i = 1; i < nums.length; i++) { if (nums[i] != nums[len]) { nums[++len] = nums[i]; } } return len + 1; } }
注意：首先对数组进行排序，然后不重复地放入原数组。
3.valid-palindrome（有效回文串）
给定一个字符串，判断其是否为一个回文串。只包含字母和数字，忽略大小写。你是否考虑过，字符串有可能是空字符串？这是面试过程中，面试官常常会问的问题。在这个题目中，我们将空字符串判定为有效回文。
public class Solution { /** * @param s A string * @return Whether the string is a valid palindrome */ public boolean isPalindrome(String s) { // Write your code here if (s == null || s.length() == 0) { return true; } int front = 0; int end = s.length() - 1; while (front < end) { while (front < s.length() && !isValid(s.charAt(front))) { front++; } if (front == s.length()) { return true; } while (end >= 0 && !isValid(s.charAt(end))) { end--; } if (Character.toLowerCase(s.charAt(front)) != Character.toLowerCase(s.charAt(end))) { break; } else { front++; end--; } } return end <= front; } private boolean isValid(char c) { return Character.isLetter(c) || Character.isDigit(c); } }
注意：使用相向双指针front和end。当(while)front和end指针所在位置不是字母或数字时，front++（要注意front==s.length()时，说明是空字符串，返回true）,end--。当front和end所在位置是字母或数字时，判断是否相等，若不相等就break，若相等front++,end--。
Character.isLetter()是否是字母，Character.isDigit()是否是数字，Character.toLowerCase()转换成小写字母。
4.partition-array（数组划分）
给出一个整数数组 nums 和一个整数 k。划分数组（即移动数组 nums 中的元素），使得：所有小于k的元素移到左边，所有大于等于k的元素移到右边。返回数组划分的位置，即数组中第一个位置 i，满足 nums[i] 大于等于 k。你应该真正的划分数组 nums，而不仅仅只是计算比 k 小的整数数，如果数组 nums 中的所有元素都比 k 小，则返回 nums.length。
public class Solution { /** *@param nums: The integer array you should partition *@param k: As description *return: The index after partition */ public int partitionArray(int[] nums, int k) { //write your code here if (nums == null || nums.length == 0) { return 0; } int left = 0; int right = nums.length - 1; while (left <= right) { while (left <= right && nums[left] < k) { left++; } while (left <= right && nums[right] >= k) { right--; } if (left <= right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } return left; } }
注意：使用快速排序思想。
5.partition-array-ii（数组划分II）
将未排序的整数数组分为三部分：1.前面部分 < low 2.中间部分 >= low & <= high 3.尾部 > high。返回任何可能的解决方案。所有测试用例中low<=high。
public class Solution { /** * @param nums an integer array * @param low an integer * @param high an integer * @return nothing */ public void partition2(int[] nums, int low, int high) { // Write your code here if (nums == null || nums.length == 0) { return; } int left = 0; int right = nums.length - 1; int i = 0; while (i <= right) { if (nums[i] < low) { swap(nums, i, left); left++; i++; } else if (nums[i] > high) { swap(nums, i, right); right--; } else { i++; } } } private void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } }
注意：与第11题颜色分类（0,1,2）思路类似，遇到<low扔左边，遇到>= low & <= high跳过，遇到>high扔右边。使用相向指针left和right，从左到右将每个位置i的元素依次与low和high进行比较，nums[i]<low时，交换位置i和位置left上的元素，i++,left++;nums[i]>high时，交换位置i和位置right的元素，right--（此时i不更新，因为交换后此时的nums[i]可能为0或1需要重新判断）;剩下的情况i++。
6.kth-largest-element（第k大元素）【Quick Select算法】
算法思想：(1)利用快速排序的分治思想，求得待搜索数组按照的主元S[q](pivot)，以主元为界分成左右两个区间。
(2)通过比较主元的位置，判断第k个大小的数在主元左区间？在主元右区间？还是就是主元？（还要注意边界条件的判断，有可能在边界）
(3)进入子区间递归调用。
在数组中找到第k大的元素。你可以交换数组中的元素的位置。
View Code注意：left=start, right=end,在一次排序完成后right<left。然后，如果start+k-1<=right, return quickSelect(nums,start, right,k);
如果start+k->=left, return quickSelect(nums,left,end,k-(left-start))。最后返回nums[right + 1]。
7.kth-smallest-numbers-in-unsorted-array（无序数组k小元素）
找到一个无序数组中最小的K个数。
QuickSelect解法：
class Solution { /* * @param k an integer * @param nums an integer array * @return kth smallest element */ public int kthSmallest(int k, int[] nums) { // write your code here return quickSelect(nums, 0, nums.length - 1, k - 1); } public int quickSelect(int[] A, int start, int end, int k) { if (start == end) return A[start]; int left = start; int right = end; int pivot = A[(start + end) / 2]; while (left <= right) { while (left <= right && A[left] < pivot) { left++; } while (left <= right && A[right] > pivot) { right--; } if (left <= right) { int temp = A[left]; A[left] = A[right]; A[right] = temp; left++; right--; } } if (right >= k && start <= right) { return quickSelect(A, start, right, k); } else if (left <= k && left <= end) { return quickSelect(A, left, end, k); } else { return A[k]; } } };
注意：if (right >= k && start <= right) {return quickSelect(A, start, right, k); } else if (left <= k && left <= end) { return quickSelect(A, left, end, k); } else {return A[k]; } 两种情况下都返回k，理解有难度。
MaxHeap解法：
class Solution { /* * @param k an integer * @param nums an integer array * @return kth smallest element */ public int kthSmallest(int k, int[] nums) { // write your code here int length = nums.length; PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k, Collections.reverseOrder()); for (int i = 0; i < k; i++) { pq.add(nums[i]); } for (int i = k; i < length; i++) { int current = nums[i]; int root = pq.peek(); if (current < root) { // Remove head pq.poll(); // Add new node pq.add(current); } } return pq.peek(); } };
注意：使用PriorityQueue优先级队列。PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k, Collections.reverseOrder());正常情况下堆顶是最小值，在经过Collections.reverseOrder()反转之后，堆顶是最大值。首先放入k个元素，然后依次遍历剩下的元素，如果比堆顶元素小就移除原堆顶，放入新元素。最后返回堆顶元素即可。
8.partition-array-by-odd-and-even（奇偶分割数组）
分割一个整数数组，使得奇数在前偶数在后。
public class Solution { /** * @param nums: an array of integers * @return: nothing */ public void partitionArray(int[] nums) { // write your code here; if (nums == null || nums.length == 0) { return; } int odd = 0; int even = nums.length - 1; while (odd <= even) { while (odd <= even && nums[odd] % 2 == 1) { odd++; } while (odd <= even && nums[even] % 2 == 0) { even--; } if (odd <= even) { int temp = nums[odd]; nums[odd] = nums[even]; nums[even] = temp; odd++; even--; } } } }
注意：使用相向双指针odd和even记录奇数和偶数所在的位置，当odd位置不是奇数，even位置不是偶数时进行交换。
9.interleaving-positive-and-negative-numbers（交错正负数）
给出一个含有正整数和负整数的数组，重新排列成一个正负数交错的数组。不需要保持正整数或者负整数原来的顺序。
class Solution { /** * @param A: An integer array. * @return: void */ public void rerange(int[] A) { // write your code here if (A == null || A.length == 0) { return; } int posNum = 0; int negNum = 0; for (int i = 0; i < A.length; i++) { if (A[i] > 0) { posNum++; } else { negNum++; } } int posIndex = 0; int negIndex = 1; if (negNum > posNum) { posIndex = 1; negIndex = 0; } while (posIndex < A.length && negIndex < A.length) { while (posIndex < A.length && A[posIndex] > 0) { posIndex += 2; } while (negIndex < A.length && A[negIndex] < 0) { negIndex += 2; } if (negIndex < A.length && posIndex < A.length) { int temp = A[negIndex]; A[negIndex] = A[posIndex]; A[posIndex] = temp; posIndex += 2; negIndex += 2; } } } }
注意：使用相向双指针posIndex和negIndex记录正整数和负整数所在的位置。首先统计正整数和负整数的数量，如果正整数的数量大于负整数的数量,则posIndex=0,negIndex=1,否则反之。当posIndex位置不是正数，negIndex位置不是负数时进行交换。特别注意位置的变化每次加2，因为是正负数交错的数组。
10.sort-letters-by-case（字符大小写排序）
给定一个只包含字母的字符串，按照先小写字母后大写字母的顺序进行排序。小写字母或者大写字母他们之间不一定要保持在原始字符串中的相对位置。
public class Solution { /** *@param chars: The letter array you should sort by Case *@return: void */ public void sortLetters(char[] chars) { //write your code here int lower = 0; int upper = chars.length - 1; while (lower <= upper) { while (lower <= upper && Character.isLowerCase(chars[lower])) { lower++; } while (lower <= upper && Character.isUpperCase(chars[upper])) { upper--; } if (lower <= upper) { char temp = chars[lower]; chars[lower] = chars[upper]; chars[upper] = temp; lower++; upper--; } } } }
注意：使用相向双指针lower和upper记录小写字母和大写字母所在位置，当lower位置不是小写字母，upper位置不是大写字母时进行交换。
Character.isLowerCase()判断是否是小写字母，Character.isUpperCase()判断是否是大写字母。
11.sort-colors（颜色分类）
给定一个包含红,白,蓝且长度为n的数组，将数组元素进行分类使相同颜色的元素相邻，并按照红、白、蓝的顺序进行排序。我们可以使用整数 0,1和2分别代表红,白,蓝。不能使用代码库中的排序函数来解决这个问题。排序需要在原数组中进行。
class Solution { /** * @param nums: A list of integer which is 0, 1 or 2 * @return: nothing */ public void sortColors(int[] nums) { // write your code here if (nums == null || nums.length == 0) { return; } int left = 0; int right = nums.length - 1; int i = 0; while (i <= right) { if (nums[i] == 0) { swap(nums, i, left); i++; left++; } else if (nums[i] == 1) { i++; } else { swap(nums, i, right); right--; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
注意：基本思路为遇到0时扔左边，遇到1时跳过，遇到2时扔右边。使用相向指针left和right，从左到右将每个位置i的元素依次与0,1,2进行比较，nums[i]=0时，交换位置i和位置left上的元素，i++,left++;nums[i]=1时，i++;nums[i]=2时，交换位置i和位置right的元素，right--（此时i不更新，因为交换后此时的nums[i]可能为0或1需要重新判断）。
12.sort-colors-ii（颜色分类II）
给定一个有n个对象（包括k种不同的颜色，并按照1到k进行编号）的数组，将对象进行分类使相同颜色的对象相邻，并按照1,2，...k的顺序进行排序。不能使用代码库中的排序函数来解决这个问题。k <= n。
【Rainbow Sort】解法：基于比较的最佳算法。
class Solution { /** * @param colors: A list of integer * @param k: An integer * @return: nothing */ public void sortColors2(int[] colors, int k) { // write your code here if (colors == null || colors.length == 0) { return; } rainbowSort(colors, 0, colors.length - 1, 1, k); } public void rainbowSort(int[] colors, int left, int right, int colorFrom, int colorTo) { if (colorFrom == colorTo) { return; } if (left >= right) { return; } int start = left; int end = right; int colorMid = (colorFrom + colorTo) / 2; while (start <= end) { while (start <= end && colors[start] <= colorMid) { start++; } while (start <= end && colors[end] > colorMid) { end--; } if (start <= end) { int temp = colors[start]; colors[start] = colors[end]; colors[end] = temp; start++; end--; } } rainbowSort(colors, left, end, colorFrom, colorMid); rainbowSort(colors, start, right, colorMid + 1, colorTo); } }
注意：时间复杂度为0(nlogk)。Rainbow Sort主体算法与快速排序类似，增加了colorFrom和colorTo参数（有具体的数值，本题中初始为1和k）。
一次排序完成后end<start，递归部分：rainbowSort(colors, left, end, colorFrom, colorMid); rainbowSort(colors, start, right, colorMid + 1, colorTo);
另一种解法：
class Solution { /** * @param colors: A list of integer * @param k: An integer * @return: nothing */ public void sortColors2(int[] colors, int k) { // write your code here int count = 0; int start = 0; int end = colors.length - 1; while (count < k) { int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for (int i = start; i <= end; i++) { min = Math.min(min, colors[i]); max = Math.max(max, colors[i]); } int left = start; int right = end; int cur = left; while (cur <= right) { if (colors[cur] == min) { swap(left, cur, colors); cur++; left++; } else if (colors[cur] > min && colors[cur] < max) { cur++; } else { swap(cur, right, colors); right--; } } count += 2; start = left; end = right; } } private void swap(int left, int right, int[] colors) { int temp = colors[left]; colors[left] = colors[right]; colors[right] = temp; } }
注意：时间复杂度为0(nk)，效率不高，会得到超时限制错误。但是应该尝试实现以下算法来达到练习的目的。
与第10题类似的思路，count记录已排序颜色数字的数目，每次+2（每次只排当前最大和最小的颜色数字）继续排。start和end记录此次排序中开始和结束颜色数字的位置，注意每次排序后要更新start和end。使用相向指针left和right，从左到右将每个位置cur的元素依次与min,>min && < max,max进行比较，colors[cur]=min时，交换位置cur和位置left上的元素，cur++,left++;colors[cur]>min && < max时，cur++;colors[cur]=max时，交换位置cur和位置right的元素，right--（此时cur不更新）。
13.two-sum（两数之和）
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 1 到 n，不是以 0 开头。你可以假设只有一组答案。
public class Solution { /* * @param numbers : An array of Integer * @param target : target = numbers[index1] + numbers[index2] * @return : [index1 + 1, index2 + 1] (index1 < index2) */ public int[] twoSum(int[] numbers, int target) { // write your code here int[] result = new int[2]; if (numbers == null || numbers.length < 2) { return result; } HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < numbers.length; i++) { if (map.containsKey(numbers[i])) { result[0] = map.get(numbers[i]) + 1; result[1] = i + 1; } map.put(target - numbers[i], i); } return result; } }
注意：使用HashMap<Integer, Integer>保存target-nums[i]与i。eg:将7存入，当再次遇到7时，取出7存入的位置和当前位置都加一后返回即可。
14.two-sum-data-structure-design（两数之和-数据结构设计）【只能使用HashMap】
设计并实现一个TwoSum类。它应该支持以下操作：添加和查找。add-将数字添加到内部数据结构。find-查找是否存在任何一对数字，其总和等于该值，返回true或false。
public class TwoSum { private List<Integer> list; private HashMap<Integer, Integer> map; // Add the number to an internal data structure. public TwoSum(){ list = new ArrayList<Integer>(); map = new HashMap<Integer, Integer>(); } public void add(int number) { // Write your code here if (map.containsKey(number)) { map.put(number, map.get(number) + 1); } else { list.add(number); map.put(number, 1); } } // Find if there exists any pair of numbers which sum is equal to the value. public boolean find(int value) { // Write your code here for (int i = 0; i < list.size(); i++) { int num1 = list.get(i); int num2 = value - num1; if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2))) { return true; } } return false; } } // Your TwoSum object will be instantiated and called as such: // TwoSum twoSum = new TwoSum(); // twoSum.add(number); // twoSum.find(value);
注意：使用HashMap<Integer, Integer>存储数字和出现次数，使用list存储数字。add()函数：一个新数字如果map里没有，就放入map和list；如果map里存在，出现次数就加一。find()函数：对list中每个数字num1求num2=value-num1,如果num1和num2相等，且num1在map中出现的次数大于1或者num1和num2不相等，num2在map中也出现则返回ture,否则返回false。
15.two-sum-input-array-is-sorted（两数之和-输入数组已排序）【使用two pointers更快】
给定一个已经按升序排序的整数数组，找到两个数字，使它们相加等于一个特定的目标数。函数twoSum应该返回两个数字的索引，使它们相加等于目标，其中index1必须小于index2。请注意，您返回的答案（index1和index2）都不是基于零的。你可以假设每个输入都只有一个解决方案。
public class Solution { /* * @param nums an array of Integer * @param target = nums[index1] + nums[index2] * @return [index1 + 1, index2 + 1] (index1 < index2) */ public int[] twoSum(int[] nums, int target) { // write your code here int[] result = new int[2]; if (nums == null || nums.length == 0) { return result; } int start = 0; int end = nums.length - 1; while (start <= end) { int sum = nums[start] + nums[end]; if (sum == target) { result[0] = start + 1; result[1] = end + 1; return result; } else if (sum < target) { start++; } else { end--; } } return result; } }
注意：使用相向双指针start和end，求和nums[start]+nums[end]=sum，如果sum==target，返回[start+1, end+1]；sum<target,start++；sum>target,end--。
16.two-sum-unique-pairs（两数之和-独特对）
给定一个整数数组，找出数组中有多少唯一对，使得它们的和等于一个特定的目标数，请返回成对数。
public class Solution { /** * @param nums an array of integer * @param target an integer * @return an integer */ public int twoSum6(int[] nums, int target) { // Write your code here if (nums == null || nums.length == 0) { return 0; } Arrays.sort(nums); int count = 0; int start = 0; int end = nums.length - 1; while (start < end) { int sum = nums[start] + nums[end]; if (sum == target) { count++; start++; end--; while (start < end && nums[start] == nums[start - 1]) { start++; } while (start < end && nums[end] == nums[end + 1]) { end--; } } else if (sum < target) { start++; } else { end--; } } return count; } }
注意：使用count记录唯一对的数目。先对数组进行排序。使用相向双指针start和end，先求和nums[start]+nums[end]=sum，如果sum==target，count加1，用“选代表法”去重（nums[start] == nums[start-1] start++，nums[end] == nums[end+1] end--）；sum<target,start++；sum>target,end--。
(1)条件为start<end,不能是start=end。eg:[1,0,-1] 0 [0,0]也会被算进去。
(2)不能先去重。eg:[7,11,11,1] 22 先去重[11,11]的解就没有了。
17.3sum（三数之和）
给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a+b+c=0的三元组。在三元组(a, b, c)，要求a<=b<=c。结果不能包含重复的三元组。
public class Solution { /** * @param numbers : Give an array numbers of n integer * @return : Find all unique triplets in the array which gives the sum of zero. */ public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) { // write your code here ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(); if (numbers == null || numbers.length < 3) { return results; } Arrays.sort(numbers); int target = 0; for (int i = 0; i < numbers.length - 2; i++) { if (i > 0 && numbers[i] == numbers[i - 1]) { continue; } int left = i + 1; int right = numbers.length - 1; while (left < right) { int sum = numbers[i] + numbers[left] + numbers[right]; if (sum == target) { ArrayList<Integer> trip = new ArrayList<Integer>(); trip.add(numbers[i]); trip.add(numbers[left]); trip.add(numbers[right]); results.add(trip); left++; right--; while (left < right && numbers[left] == numbers[left - 1]) { left++; } while (left < right && numbers[right] == numbers[right + 1]) { right--; } } else if (sum < target) { left++; } else { right--; } } } return results; } }
注意：先对数组进行排序。先跳过第一个元素重复的三元组：
for (int i = 0; i < numbers.length - 2; i++) {
if (i > 0 && numbers[i] == numbers[i - 1]) {
continue;
}
......
}然后使用与15题中类似的方法找到其余两个元素（在sum=target时最后两个元素也要去重）。
18.two-sum-less-than-or-equal-to-target（两数之和-所有和≤target的配对数）
给定整数数组，找到数组中有多少对，使得它们的和小于或等于特定目标值。请返回成对数。
public class Solution { /** * @param nums an array of integer * @param target an integer * @return an integer */ public int twoSum5(int[] nums, int target) { // Write your code here if (nums == null || nums.length < 2) { return 0; } Arrays.sort(nums); int count = 0; int left = 0; int right = nums.length - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum > target) { right--; } else { count += right - left; left++; } } return count; } }
注意：使用count记录成对数。先对数组进行排序。当nums[left]+nums[right]<=target时，有right-left个符合要求的配对[固定left,right++]。
19.two-sum-greater-than-target（两数之和-所有和>target的配对数）
给定整数数组，找到数组中有多少对，使得它们的和大于特定目标值。请返回成对数。
public class Solution { /** * @param nums: an array of integer * @param target: an integer * @return: an integer */ public int twoSum2(int[] nums, int target) { // Write your code here if (nums == null || nums.length < 2) { return 0; } Arrays.sort(nums); int count = 0; int left = 0; int right = nums.length - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum <= target) { left++; } else { count += right - left; right--; } } return count; } }
注意：使用count记录成对数。先对数组进行排序。当nums[left]+nums[right]>target时，有right-left个符合要求的配对[固定right,left++]。
20.two-sum-closest-to-target（两数和的最接近值）
找到两个数字使得他们和最接近target，返回这个差值。
public class Solution { /** * @param nums an integer array * @param target an integer * @return the difference between the sum and the target */ public int twoSumClosest(int[] nums, int target) { // Write your code here if (nums == null || nums.length < 2) { return -1; } Arrays.sort(nums); int left = 0; int right = nums.length - 1; int diff = Integer.MAX_VALUE; while (left < right) { int sum = nums[left] + nums[right]; if (sum < target) { diff = Math.min(diff, target - sum); left++; } else { diff = Math.min(diff, sum - target); right--; } } return diff; } }
注意：先对数组进行排序。使用diff变量（初始化为Integer.MAX_VALUE）记录这个差值，返回最小的差值。
21.3sum-closest（最接近的三数之和）
给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，返回这三个数的和。只需要返回三元组之和，无需返回三元组本身。
public class Solution { /** * @param numbers: Give an array numbers of n integer * @param target : An integer * @return : return the sum of the three integers, the sum closest target. */ public int threeSumClosest(int[] numbers, int target) { // write your code here if (numbers == null || numbers.length < 3) { return -1; } Arrays.sort(numbers); int bestSum = numbers[0] + numbers[1] + numbers[2]; for (int i = 0; i < numbers.length - 2; i++) { int start = i + 1; int end = numbers.length - 1; while (start < end) { int sum = numbers[i] + numbers[start] + numbers[end]; if (Math.abs(target - sum) < Math.abs(target - bestSum)) { bestSum = sum; } if (sum < target) { start++; } else { end--; } } } return bestSum; } }
注意：先对数组进行排序。在每次固定第一个元素的情况下：
for (int i = 0; i < numbers.length - 2; i++) {
int start = i + 1;
int end = numbers.length - 1;
......
}然后使用与15题中类似的方法找到其余两个元素。初始sum为前三个元素的和，然后逐渐找到与target最接近的bestSum。
22.4sum（四数之和）
给一个包含n个数的整数数组S，在S中找到所有使得和为给定整数target的四元组(a, b, c, d)。四元组(a, b, c, d)中，需要满足a <= b <= c <= d。答案中不可以包含重复的四元组。
public class Solution { /** * @param numbers : Give an array numbersbers of n integer * @param target : you need to find four elements that's sum of target * @return : Find all unique quadruplets in the array which gives the sum of * zero. */ public ArrayList<ArrayList<Integer>> fourSum(int[] numbers, int target) { /* your code */ ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(); if (numbers == null || numbers.length < 4) { return results; } Arrays.sort(numbers); for (int i = 0; i < numbers.length - 3; i++) { if (i > 0 && numbers[i] == numbers[i - 1]) { continue; } for (int j = i + 1; j < numbers.length - 2; j++) { if (j > i + 1 && numbers[j] == numbers[j - 1]) { continue; } int start = j + 1; int end = numbers.length - 1; while (start < end) { int sum = numbers[i] + numbers[j] + numbers[start] + numbers[end]; if (sum == target) { ArrayList<Integer> list = new ArrayList<Integer>(); list.add(numbers[i]); list.add(numbers[j]); list.add(numbers[start]); list.add(numbers[end]); results.add(list); start++; end--; while (start < end && numbers[start] == numbers[start - 1]) { start++; } while (start < end && numbers[end] == numbers[end + 1]) { end--; } } else if (sum < target) { start++; } else { end--; } } } } return results; } }
注意：先对数组进行排序。然后在固定第一个元素并去重的情况下，固定第二个元素并去重：
for (int i = 0; i < numbers.length - 3; i++) {
if (i > 0 && numbers[i] == numbers[i - 1]) {
continue;
}
for (int j = i + 1; j < numbers.length - 2; j++) {
if (j != i + 1 && numbers[j] == numbers[j - 1]) {
continue;
}
.......
}
}最后使用与15题中类似的方法找到其余两个元素（在sum=target时最后两个元素也要去重）。
23.two-sum-difference-equals-to-target（两数之和-差值等于目标值）
给定整数数组,找到两个数字,它们的差值等于目标值。其中index1必须小于index2。请注意您返回的答案（index1和index2是位置信息）都不是基于零的。保证只有一个可用的解决方案。
class Pair { public int index; public int num; public Pair(int index, int num) { this.index = index; this.num = num; } } public class Solution { /* * @param nums an array of Integer * @param target an integer * @return [index1 + 1, index2 + 1] (index1 < index2) */ public int[] twoSum7(int[] nums, int target) { // write your code here int[] result = new int[2]; if (nums == null || nums.length < 2) { return result; } if (target < 0) { target = -target; } int n = nums.length; Pair[] pairs = new Pair[n]; for (int i = 0; i < n; i++) { pairs[i] = new Pair(i, nums[i]); } Arrays.sort(pairs, new Comparator<Pair>() { public int compare(Pair a, Pair b) { return a.num - b.num; } }); for (int i = 0; i < n; i++) { int j = i + 1; while (j < n && pairs[j].num - pairs[i].num < target) { j++; } if (j < n && pairs[j].num - pairs[i].num == target) { result[0] = pairs[i].index + 1; result[1] = pairs[j].index + 1; if (result[0] > result[1]) { int temp = result[0]; result[0] = result[1]; result[1] = temp; } return result; } } return result; } }
注意：若目标值为负数时，要转化为正数。使用class Pair{public int num; public int index}记录每个数字和在原数组中的位置，重新定义Pair类型的数组pairs，对数组中的元素按照从小到大进行排序。Arrays.sort(要排序的数组名, new Comparator<数组类型>(){public int compare(数组类型 a, 数组类型 b){return a.num - b.num;} });然后固定位置i的数字，移动位置j=i+1的数字来寻找符合条件的两个位置。
24.triangle-count（三角形计数）
给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形？
例如，给定数组 S = {3,4,6,7}，返回 3。其中我们可以找到的三个三角形为：{3,4,6}{3,6,7}{4,6,7}
给定数组 S = {4,4,4,4}, 返回 4。其中我们可以找到的三个三角形为：{4(1),4(2),4(3)}{4(1),4(2),4(4)}{4(1),4(3),4(4)}{4(2),4(3),4(4)}
public class Solution { /** * @param S: A list of integers * @return: An integer */ public int triangleCount(int S[]) { // write your code here if (S == null || S.length < 3) { return 0; } Arrays.sort(S); int count = 0; int left = 0; int right = S.length - 1; for (int i = 0; i < S.length; i++) { left = 0; right = i - 1; while (left < right) { if (S[left] + S[right] <= S[i]) { left++; } else { count += right - left; right--; } } } return count; } }
注意：与19题思路类似，找两边之和>第三边的成对数。使用count记录成对数。先对数组进行排序。在固定第三条边（i）的基础上，寻找另外两条符合要求的边（left和right）:
for (int i = 0; i < S.length; i++) {
left = 0;
right = i - 1;
......
}当S[left]+S[right]≤S[i]时，left++;当S[left]+S[right]>S[i]时，有right-left个符合要求的成对数。