leetcode 1 ：Two Sum（返回索引）

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the sameelement twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].

实现1：暴力破解法

public int[] twoSum(int[] nums, int target) {	 int[] ret=new int[2];	  for(int i=0;i

实现2：Hashmap空间换时间

在hashmap中以数的值为key，index为value，每次检测是否有target-值得key，时间o(n)

public int[] twoSum(int[] nums, int target) {	int[] ret=new int[2];	HashMap
   
     map=new HashMap
    
     ();	for(int i=0;i

167. Two Sum II - Input array is sorted（返回索引）

本题的扩展题：

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the sameelement twice.

Example:

Input: numbers = [2,7,11,15], target = 9Output: [1,2]Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

实现1：双指针法

class Solution {    public int[] twoSum(int[] numbers, int target) {        int[] res = new int[2];        int low = 0;        int high = numbers.length - 1;        while(low < high){            if(numbers[low] + numbers[high] < target){                    low++;                }else if(numbers[low] + numbers[high] > target){                    high--;                }else{                    res[0] = low + 1;                    res[1] = high + 1;                    break;                }            }            return res;    }}

15. 3Sum（返回满足条件的元素）

本题的变形题：

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is:[  [-1, 0, 1],  [-1, -1, 2]]

思路：

1. 对数组进行排序。

2.固定住其中一个数，然后对数组中剩下的数用TwoSum==target的方式解决。（）

3. 因为数组中存在相同的数，为了避免出现相同的答案，需要跳过数组中相同的元素。

import java.util.LinkedList;import java.util.List;import java.util.Arrays;/* 1.对数组元素进行排序。 * 2.固定住一个数，对后面的元素进行遍历，寻找满足条件的twoSum==target的值（leetcode167） * 3.当两数之和满足条件，且存在重复的数时，则跳过重复的数（因为输出的是元素值，重复元素会有重复结果。）*/public class ThreeSumDemo {	public List
   
    
     > threeSum(int[] nums,int target) {	 Arrays.sort(nums);	 List
     
      
       > res=new LinkedList<>();	 for (int i = 0; i < nums.length-2; i++) {		 if(i==0||(i>0&&nums[i]!=nums[i-1])){			 //为什么只需要从固定数的后面开始寻找而不管前面的数呢？因为前面的之前已经遍历过了，			 //如果存在可行解的话也已经加入到list中了，所以只需要遍历后半截即可			 int low=i+1,high=nums.length-1,sum=target-nums[i];			 while(low

18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in numssuch that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is:[  [-1,  0, 0, 1],  [-2, -1, 1, 2],  [-2,  0, 0, 2]]

思路：

本题解法和2Sum，3Sum的思路是一样的。

* step1:数组进行排序；

* step2:二重循环，从头开始遍历，固定其中的2个数，然后再数组中寻找和为target减去这两个数的2Sum。

* （将问题转换为2Sum问题）

实现：

import java.util.List;import java.util.Arrays;import java.util.LinkedList;public class FourSumDemo {	public List
   
    
     > fourSum(int[] nums, int target) {	List
     
      
       > res=new LinkedList<>();	Arrays.sort(nums);	for (int i = 0; i < nums.length-3; i++) {		if(i>0&&nums[i]==nums[i-1]){			continue;		}		for (int j = i+1; j < nums.length-2; j++) {			if(j>1&&nums[j]==nums[j-1]&&j-i>1){				continue;			}			//已经固定好了前个数，在后面的数中进行2Sum			int low=j+1,high=nums.length-1,sum=target-nums[i]-nums[j];			while(low

总结：Ksum的题目

通过上面的2Sum，3Sum，4Sum，我们发现大于2时问题最终都转换为2Sum。

那么所有的Ksum问题都可以转换为以下2个问题：

1. 2Sum的问题；

2. 将KSum的问题转换为（K-1）Sum的问题

因此我们可以用递归来解决这个问题，时间复杂度是o(N^(K-1)).

KSum 的实现：

import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class kSumDemo2 { private ArrayList
   
    
     > kSum(int[] nums, int target, int k, int index) {	 int len=nums.length;	 ArrayList
     
      
       > res = new ArrayList
       
        
         >(); //2Sum问题 if(k == 2) { int low = index, high = len - 1; while(low < high) { //find a pair if(target - nums[low] == nums[high]) { List
         
           temp = new ArrayList<>(); temp.add(nums[low]); temp.add(target-nums[low]); res.add(temp); //若存在重复的数，则跳过 while(low
          
            nums[high]) { low++; //move right bound } else { high--; } } } else{//Ksum问题，转换为2Sum问题 for (int i = index; i < len - k + 1; i++) { //固定当前的数，将KSum减到K-1Sum ArrayList
           
            
             > temp = kSum(nums, target - nums[i], k-1, i+1); if(temp != null){ //add previous results for (List
             
               t : temp) { t.add(0, nums[i]); } res.addAll(temp); } while (i < len-1 && nums[i] == nums[i+1]) { //skip duplicated numbers i++; } } } return res; } public static void main(String[] args) { kSumDemo2 ksd=new kSumDemo2(); int[] nums={1, 0, -1, 0, -2, 2}; Arrays.sort(nums); System.out.println(ksd.kSum(nums, 0, 4, 0));}}