两数之和编程题

Question

给定一个整数数组 nums 和一个目标值 target ，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例: 给定 nums = \[2, 7, 11, 15\], target = 9 因为 nums\[0\] + nums\[1\] = 2 + 7 = 9 所以返回 \[0, 1\]

回答后才能看到答案和解析

Answer 1

一开始用首尾递进查找做的，需要一次排序，时间复杂度是 O(nlogn)，下面是 Python3 代码：


class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
sorted_id = sorted(range(len(nums)), key=lambda k: nums[k])
head = 0
tail = len(nums) - 1
sum_result = nums[sorted_id[head]] + nums[sorted_id[tail]]
while sum_result != target:
if sum_result > target:
tail -= 1
elif sum_result < target:
head += 1
sum_result = nums[sorted_id[head]] + nums[sorted_id[tail]]
return [sorted_id[head], sorted_id[tail]]

后来看解答发现可以用字典做，时间复杂度是 O(n)，还是太年轻：

Answer 2


function name (nums, target) {
nums.forEach((value,index,arr) => {
let a = arr.indexOf(target-value, index+1)
if (a >= 0) {
console.log(index,a)
}
})
}

Answer 3


public class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Hello World");
    }
}

以上是题目中含有代码的写法，了解后请删除，按照自己需求编写。

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

int n = nums.size();

vector<int> index;

for(int i = 0;i<n-1;i++)

{

int last = target - nums.at(i);

for(int j = i+1;j<n;j++)

{

if(nums.at(j) == last)

{

index.push_back(i);

index.push_back(j);

return index;

}

return index;

}

};

Answer 4

$num = [11, 15, 2, 7];

var_dump(get($num, 9));

Answer 5

for ($i = 0; $i < count($nums); $i++) { for ($j=$i+1; $j<count($nums); $j++) { if ($nums[$i] + $nums[$j] == $target) { echo "[$i,$j]\n"; return true; } } }

Answer 6

item为数组下标

两数之和 编程题

两数之和编程题