1. [LeetCode] Two Sum两数相加

缺乏、安全感 2022-03-01 06:50 131阅读 0赞

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 *same* element twice.

**Example:**

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

解法：

1. 暴力解法，两个for循环遍历，两个数相加和目标数比较。Time: O(n^2)

2. 先对数组快速排序，然后用两个指针分别指向头和尾，每次比较头尾两个数的和，如果比target小，头标记右移，如果大，尾标记左移。需要注意记录快速排序前后数字的位置变化。Time: O(n)

3. 先遍历一遍数组，建立数字和index的HashMap，然后再遍历一遍，开始查找target - num\[i\]是否在map中，如果在，找到并返回index。Time: O(n)  Space: O(n)

C语言的暴力解决：

/*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 same element twice.
    Example:
    Given nums = [2, 7, 11, 15], target = 9,
    
    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].*/ 
    #include<stdio.h>
    #include<stdlib.h>
    int* twoSum(int* nums, int numsSize, int target) {
        int i = 0, j = 0;
        int n = numsSize;
        int* result = NULL;
        for(i = 0; i < n; i++) {
            for(j = i + 1; j < n; j++) {
                if(target == nums[i] + nums[j]) {
                    result = (int*)malloc(sizeof(int) * 2);
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }
    
    int main(){	
    	int nums[4]={2,7,11,13};
    	int tag = 9;
    	int *num = twoSum(nums,4,tag);
    	printf("%d-%d",num[0],num[1]);
    	return 0;
    }

python3：

class Solution:
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            hash_map = dict()
            print(type(hash_map))
            for i, x in enumerate(nums):
                if target - x in hash_map:
                    return [i, hash_map[target-x]]
                hash_map[x] = i
    if __name__=='__main__':
        nums = [2, 7, 11, 15]
        target = 9
        p = Solution()
        print(p.twoSum(nums,target))