leedcode刷题笔记day1

题目大意：
在这里插入图片描述

暴力解法
两个for循环（也是我一看到题目想到的方法）

枚举在数组中所有的不同的两个下标的组合逐个检查它们所对应的数的和是否等于 target
复杂度分析
时间复杂度:O(n2)，这里 n 为数组的长度
空间复杂度:O(1)，只用到常数个临时变量

// public class Solution {
//     public int[] twoSum(int[] nums,int target) {
//         int len = nums.length;

//         for (int i=0; i < len-1; i++){
//             for (int j = i + 1; j < len; j++){
//                 if (nums[i] + nums[j] == target){
//                     return new int[]{i,j};
//                 }
//             }
//         }

//         throw new IllegalArgumentException("No two sum solution");
//     }
// }

使用哈希表
为了省去一层循环–>以空间换时间
在这里插入图片描述
它的逻辑就是首先让6这个key以及对应的下标value存入哈希表，然后接下来的一个元素是3，与其对应的元素就是8-3=5，而5不在目前的哈希表中，所以将3以及对应下标存入哈希表中，接下来是8,8-8=0,0也不在哈希表中，将8以及对应下标存入哈希表中，接下来是元素2,8-2=6,6在哈希表中，因此2和6就是我们要找的元素，将他们的下标【0,3】返回输出，算法结束。
在这里插入图片描述

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

public class Solution {
    public int[] twoSum(int[] nums,int target){
        int len = nums.length;
        Map<Integer,Integer> hashMap = new HashMap<>(len - 1);
        hashMap.put(nums[0],0);
        for (int i = 1;i < len;i++){
            int another = target - nums[i];
            if (hashMap.containsKey(another)){
                return new int[]{i,hashMap.get(another)};
            }
            hashMap.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

在这里插入图片描述
看见的一个比较有意思的解法
从人工推导到编程实现的过程~

代码块
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 遍历列表
        for i in range(len(nums)):
            # 计算需要找到的下一个目标数字
            res = target-nums[i]
                # 遍历剩下的元素，查找是否存在该数字
            if res in nums[i+1:]:
                # 若存在，返回答案。这里由于是两数之和，可采用.index()方法
                # 获得目标元素在nums[i+1:]这个子数组中的索引后，还需加上i+1才是该元素在nums中的索引
                return [i, nums[i+1:].index(res)+i+1]

作者：从前的我——再次回归
链接：https://leetcode.cn/problems/two-sum/solutions/1463966/jian-dan-python-by-chanemo-muld/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

python哈希表比官方分高！！！官方的哈希表才击败80%，而且比官方的容易懂！

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        mp = {}
        for i in range(n):
            t = target - nums[i]
            if t in mp:
                return [mp[t], i]
            # 存放nums[i]
            mp[nums[i]] = i
        return []