题目: 两数之和

来自智得网
跳转至： 导航、​ 搜索

分析

在集合中求解都可以采用暴力破解法解决。

暴力破解

两数之和问题是求解给定的数组中是否有和为目标值的两个数，所以最简单的思路是将任意两个数都相加，然后判断这些和的值是否目标值，这个方法是穷举（暴力破解）的方法。

暴力破解组合了集合中任意两个数字，所以一共计算的次数是，也就是，暴力破解的实现需要轮询所有的二元组，所以需要两轮循环，时间复杂度是Θ（n2）。

暴力破解的过程中，需要一个变量存储计算的和，所以空间复杂度是Θ（1）。

双指针

给定的目标是是无序的，所以暴力破解的循环成本较高。如果数组是已经排序的，那么我们可以使用双指针分别指向数据的头部和尾部，然后计算两个指针指向数据的和，利用加法的单调性，如果两数之和大于目标值，则将尾部指针向左移动，反之如果两数之和小于目标值，则将指向头部的指针右移。

双指针解法的前提是进行一轮排序操作，排序的时间复杂度是。之后对排序操作的结果进行一轮遍历，该遍历过程的时间复杂度是Θ(n)。

所以双指针法整体的时间复杂度是。

Hash法

Hash法解决两数之和

暴力破解的过程没有充分利用两数之和的特性，因为两数之和的问题具有对称性，所以遍历数组每个位置值的时候，该值和目标值的差值就可以确定了，如果在后续遍历中可以判断这个差值是否存在就可以确定是否存在满足条件的二元组。

数组是从小到后依此遍历的过程中，被遍历的值会越来越多，判断之前遍历过的元素的差值是否存在时间复杂度为Θ（n）。

为了减少遍历的成本，可以引入Hash表，Hash表可以将查询特定元素的时间复杂度从Θ（n）变成Θ（1）。

Hash表的作用是判断某个值是否存在，所以Hash表的Key就是这些值数据。因为问题需要返回二元组的位置，所以Hash表的Value可以定义为数组的位置。

所以Hash法的过程如下：

循环数组，获取目标值和当前值的差值。

在Hash表中查询该差值是否存在，如果存在则找到了符合条件的二元组，循环结束，否则将该数据以及其位置存入Hash表继续该过程。

Hash法需要做一轮完整的遍历，所以本方法的时间复杂度是Θ（n）。

Hash法需要将循环的值放入Hash表进行临时存储，所以空间复杂度也是Θ（n）。

解题

暴力破解

暴力破解使用两轮循环，外层的值是从0到n-1依此判断，内层从外层的值到n-1进行循环，依此判断这两个数字的和。

代码如下： 

public class Solution {
    public int[] solute(int[] numbers, int target){
        int length = numbers.length;
        for(int i = 0; i < length; i ++){
            int firstNumber = numbers[i];
            for(int j = i + 1; j < length; j ++){
                int secondNumber = numbers[j];
                if(firstNumber + secondNumber == target){
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }
}

双指针

此处排序过程使用快速排序。 

public class Solution {

    public static int[] solution(int[] nums, int target) {
        quickSort(nums);
        for(int i=0, j = nums.length -1; i < j; ){
            if(nums[i] + nums[j] == target){
                return new int[]{i, j};
            }else if(nums[i] + nums[j] > target){
                j--;
            }else{
                i++;
            }
        }

        return null;
    }

    private static void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length);
    }

    private static void quickSort(int nums[], int left, int right) {
        if (right <= left) {
            return;
        }

        int baseIndex = left;
        int baseNum = nums[baseIndex];
        while (left < right) {
            while (nums[right] >= baseNum) {
                right--;
            }
            while (nums[left] <= baseNum) {
                left++;
            }
            int temp = nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
        }

        int temp = nums[baseIndex];
        nums[baseIndex] = nums[left];
        nums[left] = temp;

        quickSort(nums, left + 1, nums.length - 1);
        quickSort(nums, baseIndex, right - 1);
    }
}

Hash法

具体做法是构造一个Map，遍历的时候把当前值的值和位置作为KV存入Map，同时计算目标值和当前值的差值，如果Map中存在这个差值为Key的记录，说明这两个数字的和为目标值，输出结果，结束循环。

代码如下： 

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static int[] solute(int[] nums, int target){
        Map<Integer, Integer> map = new HashMap();
        for(int i = 0; i < nums.length; i ++){
            int num = nums[i];
            if(map.get(target - num) != null){
                return new int[]{map.get(target - num), i};
            }

            map.put(num, i);
        }

        return null;
    }
}

func HashSolution(nums []int, target int)(int, int){

	store := make(map[int]int)
	for i, num := range nums{
		diff := target - num
		index, existed := store[diff]
		if existed{
			return index, i
		}else{
			store[num] = i
		}
	}

	return -1, -1
}
取自“https://www.aigetting.com/index.php?title=题目:两数之和&oldid=2065”