[LeetCode 笔记] 1. Two Sum

前言

　　我想这题是正要开始写 LeetCode 的人，大部分的人的第一题吧，这题是个基本题算在 easy 的题型，看到题目直接就会想到使用双迴圈的写法，不过双迴圈时间複杂度只有达到 O(N^2) 不那么理想，如果比较资深的工程师会用 HashMap 做处理，这时时间複杂度可以达到 N(1)，这篇有 Java 和 Python 的写法。

题目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to nums.

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

You can return the answer in any order.

给定一个整数阵列 nums 和一个整数结果 target，阵列中会有两个元素加起来等于整数结果 target，回传这两个元素的位置。

你可能假设每个输入只会对应一个答案，而且你不能使用同样的元素两次

你可以回传任何顺序的答案。

题目连结：https://leetcode.com/problems/two-sum/

题目限制

同样的元素不能使用两次

2 <= nums.length <= 104
109 <= nums[i] <= 109
109 <= target <= 109

範例

    Input: nums = [2,7,11,15], target = 9    Output: [0,1]    Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

    Input: nums = [3,2,4], target = 6    Output: [1,2]

    Input: nums = [3,3], target = 6    Output: [0,1]

思路&笔记

使用暴力的解法：双迴圈

迴圈 1 取得第一个索引，迴圈 2 取得第二个索引

但迴圈 2 的循环起始需要做个 i+1，目的是元素不要重複到

当迴圈 2 的索引都循环完后，迴圈 1 的索引会换到下一个索引，以此类推

直到两个索引的值加起来，等于目标整数 target，就把当下的索引回传出来

JAVA 初阶实现

使用暴力解法：双迴圈

    class Solution {        public int[] twoSum(int[] nums, int target) {            for (int i=0; i < nums.length; i++){                for (int j = i+1; j < nums.length; j++){ // 元素不要重複到                    if(nums[i] + nums[j] == target){                        return new int[] {i, j}; // 回传索引                    }                }            }            return new int[] {}; // 当找不到符合条件的组合时，回传一个空的整数阵列        }    }

JAVA 进阶实现

笔者还在学习中，参考了讨论区里网友的解法，这里有使用 HashMap 存资料。

如果目标整数是 9，想像一下两个数是各左右一半，那么 9 减掉其中一半会是另一半的话，答案就出来了，我们只是把答案先放在 HashMap 里的 Key 的位置， Value 是对应的索引位置，那个判断式就是判断 HashMap 里有没有另外一半，有的话把 Value 输出出来。

遍历时用 target 减掉当下索引的值，可以得出另一个整数。(这个就是我们要相加起来的另一个整数，没有的话代表不是两数的合)因第一次判断 Map 本来就是空的一定不成功，所以把已判断过的元素跟索引存进 Map 里。(这里要颠倒存，因为之后判断时要取索引，索引放在值的地方)之后遍历第二次时，判断 .containsKey() 搜寻 Map 里有无 key，这时 true 进入判断式.get() 取值 (刚颠倒存入的索引) → 0i 则是当下的索引 → 1最后把两个索引存入 new int[] 阵列中 [0, 1]

    import java.util.HashMap;    import java.util.Map;        class Solution {        public int[] twoSum(int[] nums, int target) {            Map<Integer, Integer> numToIndex = new HashMap<>();            for (int i = 0; i < nums.length; i++) {                // 判断键是否存在 Map                if (numToIndex.containsKey(target - nums[i])) { // 目标整数 - 索引 1 的值                    // 回传两个索引                    return new int[] {numToIndex.get(target - nums[i]), i}; // numToIndex 里的"值"是索引,当前 i 是索引                }                // 把前面的资料添加进 Map                 numToIndex.put(nums[i], i);  // {2=0} (注意这边是颠倒的存进去)            }            return new int[] 0; // 仍未找到符合要求的元素，则返回一个空的 int[] 阵列        }    }

Python 初阶实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def twoSum(self, nums: List[int], target: int) -> List[int]:        for i in range(len(nums)):            for j in range(i + 1, len(nums)): # 索引从第2个开始                if i != j and nums[i] + nums[j] == target: # 索引不要重複且索引值相加                    return [i, j]return []

Python 进阶实现

笔者还在学习中，参考了讨论区里网友的解法。
使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:        def twoSum(self, nums: List[int], target: int) -> List[int]:        numToIndex = {} # 字典        for i in range(len(nums)):            # 判断键是否存在 Map            if target - nums[i] in numToIndex: # 目标整数 - 索引 1 的值                return [numToIndex[target - nums[i]], i]             # 把前面的资料添加进字典            numToIndex[nums[i]] = i # 键 nums[i] = 值 i        return []

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/04/14/LeetCode-1-Two-Sum-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论