題目：兩數之和
描述：給定一個整數數列，找出其中和為特定值的那兩個數。
你可以假設每個輸入都隻會有一種答案，同樣的元素不能被重用。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
是以傳回 [0, 1] 代碼：
//時間複雜度O(n^2)
class Solution {
public int[] twoSum(int[] nums, int target) {
int [] result = new int[2];
for(int i=0;i<nums.length-1;i++){
for(int j=i+1;j<nums.length;j++){
if((nums[i]+nums[j])==target){
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
}
//時間複雜度O(n)
class Solution{
public int[] twoSum(int[] numbers, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; map.put(numbers[i], ++i))
if (map.containsKey(target - numbers[i]))
return new int[]{map.get(target - numbers[i])-1,i};
return new int[]{0,0};
}
}
題目：三數之和
描述：給定一個包含n個整數的數組S，書否存在屬于S的三個元素a,b,c使得a+b+c=0？找出所有三個元素不重複的組合。
注意：結果不能包括重複的三個數的組合。
例如, 給定數組 S = [-1, 0, 1, 2, -1, -4]，
一個結果集合為：
[
[-1, 0, 1],
[-1, -1, 2]
] 代碼：
//時間複雜度O(n^2)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new LinkedList<>();
for(int i=0;i<nums.length-2;i++){
if(i==0 || (i>0&&nums[i] != nums[i-1])){
int lo = i+1,hi = nums.length-1,sum = 0-nums[i];
while(lo<hi){
if((nums[lo]+nums[hi])==sum){
list.add(Arrays.asList(nums[i],nums[lo],nums[hi]));
while((lo<hi)&&(nums[hi]==nums[hi-1]))
hi--;
while((lo<hi)&&(nums[lo]==nums[lo+1]))
lo++;
lo++;
hi--;
}
else if((nums[lo]+nums[hi])<sum){
lo++;
}
else
hi--;
}
}
}
return list;
}
}
題目：四數之和
描述：給定一個含有 n 個整數的數組 S，數列 S 中是否存在元素 a，b，c 和 d 使 a + b + c + d = target ？請在數組中找出所有滿足各元素相加等于特定值 的 不重複 組合。
注意：解決方案集不能包含重複的四元組合。
例如，給定數組 S = [1, 0, -1, 0, -2, 2]，并且給定 target = 0。
示例答案為：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
] 代碼：
//時間複雜度O(n^3)
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> list = new LinkedList<>();
for(int i=0;i<nums.length-3;i++){
for(int j=i+1;j<nums.length-2;j++){
if(i==0 || (i>0)&&nums[i]!=nums[i-1])
{
int lo = j+1,hi = nums.length-1,sum = target - nums[i] - nums[j];
//if(i==0 || (i>0)&&nums[i]!=nums[i-1])
while(lo<hi){
if((nums[lo]+nums[hi])==sum){
list.add(Arrays.asList(nums[i],nums[j],nums[lo],nums[hi]));
while(j<nums.length-2 && nums[j]==nums[j+1])
j++;
while(lo<hi && nums[lo]==nums[lo+1])
lo++;
while(lo<hi && nums[hi]==nums[hi-1])
hi--;
lo++;
hi--;
}
else if((nums[lo]+nums[hi])<sum)
lo++;
else
hi--;
}
}
}
}
return list;
}
}
降階實作：
public List<List<Integer>> fourSum(int[] nums, int target) {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
int len = nums.length;
if (nums == null || len < 4)
return res;
Arrays.sort(nums);
int max = nums[len - 1];
if (4 * nums[0] > target || 4 * max < target)
return res;
int i, z;
for (i = 0; i < len; i++) {
z = nums[i];
if (i > 0 && z == nums[i - 1])// avoid duplicate
continue;
if (z + 3 * max < target) // z is too small
continue;
if (4 * z > target) // z is too large
break;
if (4 * z == target) { // z is the boundary
if (i + 3 < len && nums[i + 3] == z)
res.add(Arrays.asList(z, z, z, z));
break;
}
threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z);
}
return res;
}
public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,int z1) {
if (low + 1 >= high)
return;
int max = nums[high];
if (3 * nums[low] > target || 3 * max < target)
return;
int i, z;
for (i = low; i < high - 1; i++) {
z = nums[i];
if (i > low && z == nums[i - 1]) // avoid duplicate
continue;
if (z + 2 * max < target) // z is too small
continue;
if (3 * z > target) // z is too large
break;
if (3 * z == target) { // z is the boundary
if (i + 1 < high && nums[i + 2] == z)
fourSumList.add(Arrays.asList(z1, z, z, z));
break;
}
twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z);
}
}
public void twoSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,int z1, int z2) {
if (low >= high)
return;
if (2 * nums[low] > target || 2 * nums[high] < target)
return;
int i = low, j = high, sum, x;
while (i < j) {
sum = nums[i] + nums[j];
if (sum == target) {
fourSumList.add(Arrays.asList(z1, z2, nums[i], nums[j]));
x = nums[i];
while (++i < j && x == nums[i]) // avoid duplicate
;
x = nums[j];
while (i < --j && x == nums[j]) // avoid duplicate
;
}
if (sum < target)
i++;
if (sum > target)
j--;
}
return;
}
擴充：k數之和
List<List<Integer>> kSum_Trim(int[] a, int target, int k) {
List<List<Integer>> result = new ArrayList<>();
if (a == null || a.length < k || k < 2) return result;
Arrays.sort(a);
kSum_Trim(a, target, k, 0, result, new ArrayList<>());
return result;
}
void kSum_Trim(int[] a, int target, int k, int start, List<List<Integer>> result, List<Integer> path) {
int max = a[a.length - 1];
if (a[start] * k > target || max * k < target) return;
if (k == 2) { // 2 Sum
int left = start;
int right = a.length - 1;
while (left < right) {
if (a[left] + a[right] < target) left++;
else if (a[left] + a[right] > target) right--;
else {
result.add(new ArrayList<>(path));
result.get(result.size() - 1).addAll(Arrays.asList(a[left], a[right]));
left++; right--;
while (left < right && a[left] == a[left - 1]) left++;
while (left < right && a[right] == a[right + 1]) right--;
}
}
}
else { // k Sum
for (int i = start; i < a.length - k + 1; i++) {
if (i > start && a[i] == a[i - 1]) continue;
if (a[i] + max * (k - 1) < target) continue;
if (a[i] * k > target) break;
if (a[i] * k == target) {
if (a[i + k - 1] == a[i]) {
result.add(new ArrayList<>(path));
List<Integer> temp = new ArrayList<>();
for (int x = 0; x < k; x++) temp.add(a[i]);
result.get(result.size() - 1).addAll(temp); // Add result immediately.
}
break;
}
path.add(a[i]);
kSum_Trim(a, target - a[i], k - 1, i + 1, result, path);
path.remove(path.size() - 1); // Backtracking
}
}
}
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)