2023-9-6

9-6

两数之和

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

有点像今天做的qq音乐的题目

解法一

function twoSum(nums: number[], target: number): number[] {
    for(let i =0;i<nums.length;i++){
        for(let j = i+1;j<nums.length;j++){
            if(target===nums[i]+nums[j])return[i,j]
        }
    }
};

使用哈希表可以优化查找到taget-x的时间复杂度从O(N)到O(1)

function twoSum(nums: number[], target: number): number[] {
    const hashtable: { [key: number]: number } = {};

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (hashtable.hasOwnProperty(complement)) {
            return [hashtable[complement], i];
        }

        hashtable[nums[i]] = i;
    }

    return [];
}