Leetcode basic programming: array

1. Sum of two numbers

difficulty ： Simple

Collection

Given an array of integers nums And an integer target value target, Please find... In the array And is the target value target the Two Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

You can return the answers in any order .

Example 1：

 Input ：nums = [2,7,11,15], target = 9
 Output ：[0,1]
 explain ： because  nums[0] + nums[1] == 9 , return  [0, 1] .

Example 2：

 Input ：nums = [3,2,4], target = 6
 Output ：[1,2]

Example 3：

 Input ：nums = [3,3], target = 6
 Output ：[0,1]

Tips ：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• There will only be one valid answer

** Advanced ：** You can come up with a time complexity less than O(n2) The algorithm of ？

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result=[]
        for i in range(len(nums)-1):
            find = target - nums[i]
            for j in range(i+1,len(nums)):
                if nums[j]==find:
                    return [i,j]
        return result

15. The closest sum of three

difficulty ： secondary

Collection

Give you a length of n Array of integers for nums and A target value target. Please start from nums Choose three integers , Make their sum with target Nearest .

Returns the sum of the three numbers .

It is assumed that there is only exactly one solution for each set of inputs .

Example 1：

 Input ：nums = [-1,2,1,-4], target = 1
 Output ：2
 explain ： And  target  The closest and  2 (-1 + 2 + 1 = 2) .

Example 2：

 Input ：nums = [0,0,0], target = 1
 Output ：0

Tips ：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

class Solution:
   def threeSumClosest(self, nums: List[int], target: int) -> int:
       nums.sort()
       result=nums[0]+nums[1]+nums[2]
       for i in range(len(nums)-2):
           start=i+1
           end=len(nums)-1
           while start < end:
               sum=nums[start]+nums[end]+nums[i]
               if abs(target-sum)<abs(target-result):
                   result=sum
               if sum>target:
                   end-=1
               elif sum<target:
                   start+=1
               else:
                   return result
       return result

26. Remove elements

difficulty ： Simple

Collection

Give you an array nums And a value val, You need In situ Remove all values equal to val The elements of , And return the new length of the array after removal .

Don't use extra array space , You have to use only O(1) Additional space and In situ Modify input array .

The order of elements can be changed . You don't need to think about the elements in the array that follow the new length .

explain :

Why is the return value an integer , But the output answer is array ?

Please note that , The input array is based on **「 quote 」** By way of transmission , This means that modifying the input array in a function is visible to the caller .

You can imagine the internal operation as follows :

// nums  In order to “ quote ” By way of transmission . in other words , Do not make any copies of the arguments 
int len = removeElement(nums, val);

//  Modifying the input array in a function is visible to the caller .
//  Based on the length returned by your function ,  It prints out the array   Within this length   All elements of .
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Example 1：

 Input ：nums = [3,2,2,3], val = 3
 Output ：2, nums = [2,2]
 explain ： Function should return the new length  2,  also  nums  The first two elements in are  2. You don't need to think about the elements in the array that follow the new length . for example , The new length returned by the function is  2 , and  nums = [2,2,3,3]  or  nums = [2,2,0,0], It will also be seen as the right answer .

Example 2：

 Input ：nums = [0,1,2,2,3,0,4,2], val = 2
 Output ：5, nums = [0,1,4,0,3]
 explain ： Function should return the new length  5,  also  nums  The first five elements in are  0, 1, 3, 0, 4. Note that these five elements can be in any order . You don't need to think about the elements in the array that follow the new length .

Tips ：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums:
            nums.remove(val)
        return len(nums)

\25. Remove duplicate items from an ordered array

difficulty ： Simple

Collection

Here's an ordered array nums , Would you please ** In situ ** Delete duplicate elements , Make each element Only once , Returns the new length of the deleted array .

Don't use extra array space , You must be there. In situ Modify input array And using O(1) Complete with extra space .

explain :

Why is the return value an integer , But the output answer is array ?

Please note that , The input array is based on **「 quote 」** By way of transmission , This means that modifying the input array in a function is visible to the caller .

You can imagine the internal operation as follows :

// nums  In order to “ quote ” By way of transmission . in other words , Do not make any copies of the arguments 
int len = removeDuplicates(nums);

//  Modifying the input array in a function is visible to the caller .
//  Based on the length returned by your function ,  It prints out the array   Within this length   All elements of .
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Example 1：

 Input ：nums = [1,1,2]
 Output ：2, nums = [1,2]
 explain ： Function should return the new length  2 , And the original array  nums  The first two elements of are modified to  1, 2 . You don't need to think about the elements in the array that follow the new length .

Example 2：

 Input ：nums = [0,0,1,1,1,2,2,3,3,4]
 Output ：5, nums = [0,1,2,3,4]
 explain ： Function should return the new length  5 ,  And the original array  nums  The first five elements of are modified to  0, 1, 2, 3, 4 . You don't need to think about the elements in the array that follow the new length .

Tips ：

• 0 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums In ascending order

class Solution:
   def removeDuplicates(self, nums: List[int]) -> int:
       sets=set(nums)
       #print(sets)
       #del nums
       for i in nums[::-1]:
           nums.remove(i)
       for item in sets:
           nums.append(item)
       nums.sort()
       #print(nums)
       return len(nums)

\14. Sum of three numbers

difficulty ： secondary

Collection

Give you one containing n Array of integers nums, Judge nums Are there three elements in *a,b,c ,* bring a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .

** Be careful ：** Answer cannot contain duplicate triples .

Example 1：

 Input ：nums = [-1,0,1,2,-1,-4]
 Output ：[[-1,-1,2],[-1,0,1]]

Example 2：

 Input ：nums = []
 Output ：[]

Example 3：

 Input ：nums = [0]
 Output ：[]

Tips ：

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res=[]
        for i in range(len(nums)):
            if i and nums[i]==nums[i-1]:
                continue
            k=len(nums)-1
            for j in range(i+1,k):
                if j>i+1 and nums[j]==nums[j-1]:
                    continue
                while j<k-1 and nums[i]+nums[j]+nums[k-1]>=0:
                    k-=1
                if nums[i]+nums[j]+nums[k]==0:
                    res.append([nums[i],nums[j],nums[k]])
        return res