leetcode刷题记录19

发表于   |   分类于

介绍19

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

思路19

想了三个节省时间的点，遇到和上一个数重复的，就不用再算了，另外由于已经排好序了，可以看当前数的两倍是否大于target，如果当前数加查询的数已经大于target，也不用继续查了

代码19

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
   def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        find=False   
        for n in range(len(numbers)):
           if (n==0) or (numbers[n]!=numbers[n-1]):
             if not find:
                  if numbers[n]*2>target:
                       nums=numbers[:n]
                       base=0
                  else:
                       nums=numbers[n+1:]
                       base=n+1
                  x=numbers[n]
                  for i in range(len(nums)):
                      if i+x>target:
                            break
                      elif nums[i]+x==target:
                            r=[n+1,base+i+1]
                            r.sort()
                            find=True
                            break
             else:
                return r