乐趣区

关于leetcode:LeetCode高频算法面试题-001-两数之和

jiezi

大家好，我是散步 coding, 最近在整顿 2022 年 LeetCode 高频算法面试题 , 感觉好的, 能够点赞、珍藏哈。同时有补充的也欢送大家给出反馈。本文首发于公众号: 散步 coding

https://manbucoding.com/trave…

题目来源于 LeetCode 上第 1 号问题：两数之和。题目难度为 Easy。

题目形容

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

你能够假如每种输出只会对应一个答案。然而，你不能反复利用这个数组中同样的元素。

题目难度: ★

示例:

 给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

示例 2：

 输出：nums = [3,2,4], target = 6
输入：[1,2]

示例 3：

 输出：nums = [3,3], target = 6
输入：[0,1]

题目解析

应用查找表来解决该问题。

设置一个 map 容器 record 用来记录元素的值与索引，而后遍历数组 nums。

  • 每次遍历时应用长期变量 complement 用来保留目标值与以后值的差值
  • 在此次遍历中查找 record，查看是否有与 complement 统一的值，如果查找胜利则返回查找值的索引值与以后变量的值 i
  • 如果未找到，则在 record 保留该元素与索引值 i

代码实现

tips: 以下代码是应用 Go 代码实现的不同解法, 文章最初能够看 C ++、C、Java、Python 实现

1、暴力解法

最容易想到的办法是枚举数组中的每一个数 x，寻找数组中是否存在 target – x。

当咱们应用遍历整个数组的形式寻找 target – x 时，须要留神到每一个位于 x 之前的元素都曾经和 x 匹配过，因而不须要再进行匹配。而每一个元素不能被应用两次，所以咱们只须要在 x 前面的元素中寻找 target – x。

func twoSum(nums []int, target int) []int {numsLen := len(nums)
    for i, num := range nums {
        for j := i + 1; j < numsLen; j++ {if target == num + nums[j] {return []int{i, j}
            }
        }
    }
    return []int{}
}

执行后果 :

  • 工夫复杂度：O(N^2)，其中 N 是数组中的元素数量。最坏状况下数组中任意两个数都要被匹配一次。
  • 空间复杂度：O(1)。

内存方面还能够，不过运行工夫偏慢, 工夫复杂度太高了。

2、应用 map 形式, nums 的值进行倒排索引, 以空间换工夫，工夫复杂度是 O(n)

func twoSum(nums []int, target int) []int {numsMap := make(map[int]int)

    for index, num := range nums{numsMap[num] = index    
    }

    for index, num := range nums {if preIndex, ok := numsMap[target-num];  (ok && preIndex != index) {return []int{preIndex, index}
        } 
        
    }
    return []int{}
}

执行后果 :

工夫复杂度：O(n)，咱们只遍历了蕴含有 O(n) 个元素的列表两次。在表中进行的每次查找只破费 O(1) 的工夫。
空间复杂度：O(n)，所需的额定空间取决于哈希表中存储的元素数量，该表最多须要存储 N 个 元素。

3、应用 map 形式, nums 的值进行倒排索引，一遍哈希表

事实证明，咱们能够一次实现。在进行迭代并将元素插入到表中的同时，咱们还会回过头来检查表中是否曾经存在以后元素所对应的指标元素。如果它存在，那咱们曾经找到了对应解，并立刻将其返回。

func twoSum(nums []int, target int) []int {numsMap := make(map[int]int)
    for index, num := range nums {if preIndex, ok := numsMap[target-num]; ok {return []int{preIndex, index}
        }
        numsMap[num] = index
    }
    return []int{}
}

执行后果 :

工夫复杂度：O(n)，咱们只遍历了蕴含有 O(n) 个元素的列表一次。在表中进行的每次查找只破费 O(1) 的工夫。
空间复杂度：O(n)，所需的额定空间取决于哈希表中存储的元素数量，该表最多须要存储 N 个元素。

4、双指针游标

双指针的思路

  • 将原数组排好序, 设置两个指针 left, right
  • left 从 0 开始, right 做 len(nums) – 1 开始
  • 当 nums[left] + nums[right] < target 时，咱们就没有必要对所有的 right0 ∈(left, right)，因为 nums[left] + nums[right0] 肯定是比 target 小的, 所以 left = left + 1 后从新判断
  • 当 nums[left] + nums[right] > target 时，同样的，对 left0 ∈(left, right)，必然有 nums[left0] + nums[right] > target, 所以 right = right – 1 后从新判断
  • 当 nums[left] + nums[right] = target 时，就是咱们想要晓得的两个数值了
  • 而后利用 Map 将数值转换为之前的游标 
func twoSum(nums []int, target int) []int {
    type Node struct{
        Value int
        Next  *Node
    }
     // 用链表是解决数组反复问题
    numsMap := make(map[int]*Node)
    var current *Node
    for index, num := range nums{if _, ok := numsMap[num]; ok{current = numsMap[num]
            for {
                if current.Next == nil{current.Next = &Node{index, nil}
                    break
                }

                current = current.Next
            }
        }else{numsMap[num] = &Node{index, nil}
        }
    }

    sort.Ints(nums)
    left := 0
    right := len(nums) - 1
    for {
        if left >= right{break}

        sum := nums[left] + nums[right]
        if sum == target{if nums[left] == nums[right]{return []int{numsMap[nums[left]].Value, numsMap[nums[left]].Next.Value}
            }else{return []int{numsMap[nums[left]].Value, numsMap[nums[right]].Value}
            }

        }

        if sum < target{left ++}else{right --}
    }
    return []int{}
}

执行后果 :

因为要排序，工夫复杂度也比拟高, 须要 Map 存储游标，空间复杂度也比拟高, 算是一个不太好的实现形式。

其余语言版本

C++

// 1. Two Sum
// 工夫复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> record;
        for(int i = 0 ; i < nums.size() ; i ++){int complement = target - nums[i];
            if(record.find(complement) != record.end()){int res[] = {i, record[complement]};
                return vector<int>(res, res + 2);
            }

            record[nums[i]] = i;
        }
        return {};}
};

执行后果

C

// 1. Two Sum
// 工夫复杂度：O(n)
// 空间复杂度：O(n)
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){int *ans=(int *)malloc(2 * sizeof(int));
    int i,j;
    bool flag=false; 
    for(i=0;i<numsSize-1;i++)
    {for(j=i+1;j<numsSize;j++)
        {if(nums[i]+nums[j] == target)
            {ans[0]=i;
                ans[1]=j;
                flag=true;
            }
        }
    }
    if(flag){*returnSize = 2;}
    else{*returnSize = 0;}
    return ans;
}

执行后果

Java

// 1. Two Sum
// https://leetcode.com/problems/two-sum/description/
// 工夫复杂度：O(n)
// 空间复杂度：O(n)
class Solution {public int[] twoSum(int[] nums, int target) {
        int l = nums.length;
        int[] ans=new int[2];
        int i,j;
        for(i=0;i<l-1;i++)
        {for(j=i+1;j<l;j++)
            {if(nums[i]+nums[j] == target)
                {ans[0]=i;
                    ans[1]=j;
                }
            }
        }
        
        return ans;
        
    }
}

执行后果

Python

# 1. Two Sum
# https://leetcode.com/problems/two-sum/description/
# 工夫复杂度：O(n)
# 空间复杂度：O(n)
class Solution(object):
    def twoSum(self, nums, target):
        l = len(nums)
        print(nums)
        ans=[]
        for i in range(l-1):
            for j in range(i+1,l):
                if nums[i]+nums[j] == target:
                    ans.append(i)
                    ans.append(j)
                    print([i,j])
                    break
        return ans

执行后果

结语

综合来看，抉择形式 3 比拟好: 应用 map 形式, nums 的值进行倒排索引，一遍哈希表, Go 的实现在内存方面和工夫复杂度都还能够，Python 绝对体现就差很多。

几种语言运行成果比照

Go 程序在内存方面体现最佳, Python 在内存和运行工夫体现 比拟其余的语言都比拟差。

也欢送关注我的公众号: 散步 coding。一起交换, 在 coding 的世界里散步。

退出移动版