首页 > 代码库 > 1. Two Sum

1. Two Sum

2024-08-23 09:30:28   222人阅读

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.

假设每个输入只有一个解

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Brute Force

time complexity O(n2)
space complexity O(1)
  1. class Solution {
  2. public:
  3.     vector<int> twoSum(vector<int>& nums, int target) {
  4.         vector<int> result;
  5.         int len = nums.size();
  6.         for(int i = 0; i < len - 1; ++i){
  7.             for(int j = i + 1; j < len; ++j){
  8.                 if(nums[i]+nums[j] == target){
  9.                     result.push_back(i);
  10.                     result.push_back(j);
  11.                     return result;
  12.                 }
  13.             }
  14.         }
  15.         return result;
  16.     }
  17. };

Hash

time complexity O(n)
space complexity O(n)
该方法给出的序列是从后往前的
  1. class Solution {
  2. public:
  3.     vector<int> twoSum(vector<int>& nums, int target) {
  4.     unordered_map<int, int> imap;
  5.     for (int i = 0;; ++i) {
  6.         auto it = imap.find(target - nums[i]);        
  7.         if (it != imap.end()) 
  8.             return vector<int> {i, it->second};            
  9.         imap[nums[i]] = i;
  10.         }
  11.     }
  12. };
see discussion here https://discuss.leetcode.com/topic/3294/accepted-c-o-n-solution/2






来自为知笔记(Wiz)


1. Two Sum


联系
我们