两数之和

题目链接:https://leetcode.cn/problems/two-sum/

leetcode 编号 no.1，算是无数尝试学习算法的人迈出的第一步，本身这道题目在力扣上标记为简单，所以即使是最简单的暴力算法，时间复杂度来到 O(n^2) 也可以轻松拿捏。

以 go 语言为例这里展示两种做法

暴力枚举

func twoSum(nums []int,target int)[]int{
    result:=make([]int,2)
    for i:=0;i<len(nums);i++{
        for j:=i+1;j<len(nums);j++{
            if nums[i]+nums[j]==target{
                result[0]=i
                result[1]=j
                return result
            }
        }
    }
    return nil
}

然后这里提供一种使用散列表 (HashMap) 的解决方案，这种方案摈弃了内层循环，将其替换为使用 map 寻找 target-nums[i]的元素 (基于 map 的查询时间复杂度是常数级的)，这样大大提高了查询的效率，时间复杂度成功下降到了 O(n)

引入 hash 表

func twoSum(nums []int, target int) []int {
	result := make([]int, 0)
	map_now := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		value, ok := map_now[target-nums[i]]
		if ok {
			result = append(result, i)
			result = append(result, value)
			return result
		}
		map_now[nums[i]] = i
	}

	return nil
}

排序 + 双指针

本方法用 Java 语言编写，双指针查找是基于数组有序的方法，所以我们首先需要用快速排序对数组进行排序，这里直接调用 Java 的 API 进行排序，当我们用双指针找到这两个值以后由于本题求的是原数组下标，所以我们需要复制一个原数组，将这两个值与复制的数组遍历来找到正确的原数组下表。同时我们注意到这个题不能用两次相同的元素，所以我们还需要用一个数组来跟踪每个元素的使用情况

时间复杂度:O(nlogn) 空间复杂度 O(n) 注意这里快速排序的时间复杂度为 O(nlogn),双指针的时间复杂度为 O(n),但 nlogn > n，所以整体时间复杂度为 O(nlogn)

java

public int[] twoSum(int[] nums, int target) {
    // 创建一个与原数组相同长度的克隆数组，用于保存原始顺序
    int[] clone = new int[nums.length];
    for(int i = 0; i < nums.length; i++){
        clone[i] = nums[i];
    }
    
    // 对原数组进行排序，以便使用双指针方法查找目标和
    Arrays.sort(nums);
    
    // 初始化左指针和右指针
    int left = 0;
    int right = nums.length - 1;
    
    // 用于存储找到的两个数值
    int[] twoSum = new int[2];
    
    // 使用双指针法寻找两个数的和等于目标值
    while(left < right){
        int currentSum = nums[left] + nums[right];
        if(currentSum > target){
            // 当前和大于目标值，右指针左移以减小和
            right--;
        } else if(currentSum < target) {
            // 当前和小于目标值，左指针右移以增大和
            left++;
        } else {
            // 找到满足条件的两个数
            twoSum[0] = nums[left];
            twoSum[1] = nums[right];
            break;
        }
    }
    
    // 提取找到的两个数值
    int val0 = twoSum[0];
    int val1 = twoSum[1];
    
    // 创建一个布尔数组用于跟踪元素是否已被使用，防止重复使用同一元素
    boolean[] res = new boolean[clone.length];
    
    // 遍历克隆数组，找到第一个匹配val0的索引
    for(int i = 0; i < clone.length; i++){
        if(clone[i] == val0 && !res[i]){
            twoSum[0] = i; // 存储索引
            res[i] = true;  // 标记为已使用
            break;
        }
    }
    
    // 遍历克隆数组，找到第一个匹配val1的索引
    for(int i = 0; i < clone.length; i++){
        if(clone[i] == val1 && !res[i]){
            twoSum[1] = i; // 存储索引
            res[i] = true;  // 标记为已使用
            break;
        }
    }
    
    // 返回结果数组，包含两个目标元素的原始索引
    return twoSum;
}

思考：这里的双指针查找是一个数一个数对比查找，能否不用双指针改用二分查找进一步优化？

两数之和 ​

两数之和