【LeetCode】#1——TwoSum

03-06

QUESTION：
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].

Subscribe to see which companies asked this question.

翻譯：

給定一個整數數組，找出其中兩個數滿足相加等於你指定的目標數字。

要求：這個函數twoSum必須要返回能夠相加等於目標數字的兩個數的索引，且index1必須要小於index2。返回的結果是基於0開始的。

你可以假設每一個輸入肯定只有一個結果。

舉例：

輸入：numbers={2, 7, 11, 15}, target = 9

返回值：[0,1](不是基於0開始的)

解決：

最簡單的想法，直接兩層循環就可以完成，時間複雜度為o(n^2)，空間複雜度為o(1)，代碼如下：

class Solution {public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result;for (int i = 0; i < nums.size()-1; i++) {for (int j = i+1; j < nums.size(); j++) {if (nums[i] + nums[j]==target) {result.push_back(i);result.push_back(j);return result;}}}return result;}};