An array is a collection of objects with a certain order , The objects that make up an array are called array elements . Where the vector corresponds to a one-dimensional array , Matrix corresponding to 2D array .
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]:
answer = []
for i in range(len(nums)):# The first value is
for j in range(i+1,len(nums)):# because a+b==b+a So the second value comes after the first value
if(nums[i]+nums[j]==target):# Whether it is equal to the value to be found
answer.append(i)
answer.append(j)
return answer# Index , return
#2836 ms 15.3 MB
# advantage ： Simple 、 Understandability
# shortcoming ： The time complexity is O（n2）
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashMap = {
}# Use a dictionary to record , The value is index , The array index is a value
for i,num in enumerate(nums):# enumeration , Get the index and value at once
if hashMap.get(target-num) is not None:# Whether the corresponding value exists
return [hashMap.get(target-num), i]# There is returned
hashMap[num] = i# There is no storage
#36 ms 15.9 MB amazing！！
# advantage ： fast , The time complexity is O（n）
# shortcoming ： Space for time , It's hard to understand
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
Ideas ： The whole idea is to traverse to find all triples equal to zero , Then go heavy. . But the time complexity of violent enumeration is too high , So sort the data first , Define another element , The sum of the rest is its negative value .
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
answer = []
nums.sort()# Sort the list
for i in range(len(nums)):
target = -nums[i] # The opposite of the first value , Find the corresponding sum of the last two values
left = i + 1 # Left pointer
right = len(nums) - 1 # Right pointer
while(left<right):
sum = nums[left] + nums[right] # Sum up
if(sum == target):
if([nums[i],nums[left],nums[right]] not in answer):
answer.append([nums[i],nums[left],nums[right]])# duplicate removal
left += 1
right -= 1
elif(sum < target):# Less than expected , increase sum, Move the left pointer to the right
left += 1
else:# Greater than expected , Reduce sum, Right pointer left
right -= 1
return answer
#3236 ms 17.4 MB
# advantage ： The time complexity is O(n2), It reduces one level of time complexity compared to violent enumeration .
# shortcoming ： Slower . Not considering all kinds of situations .
1、 For an array that is empty or less than 3 Direct return null .
2、 When traversing to a positive number , Due to data sorting , The next two will not add up 0, Go straight back to
3、 After sorting, the adjacent numbers are the same , No longer match , The first number skips directly , Add more to the second number 1. There will be no repetition .
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n=len(nums)
res=[]
if(not nums or n<3):# The array length is less than 3 Or if it is empty, return directly
return []
nums.sort()# Array sorting
res=[]# result
for i in range(n):
if(nums[i]>0):# If the first number is greater than zero , The size of the last two numbers cannot be less than zero
return res
if(i>0 and nums[i]==nums[i-1]):# The same value , skip
continue
L=i+1
R=n-1
while(L<R):
if(nums[i]+nums[L]+nums[R]==0):
res.append([nums[i],nums[L],nums[R]])
while(L<R and nums[L]==nums[L+1]):# The same value , skip
L=L+1
while(L<R and nums[R]==nums[R-1]):# The same value , skip
R=R-1
L=L+1
R=R-1
elif(nums[i]+nums[L]+nums[R]>0):
R=R-1
else:
L=L+1
return res
#640 ms 17.7 MB
# advantage ： Fast .
# shortcoming ： Consider a variety of situations .
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()
answer = nums[0] + nums[1] + nums[2]# The initial solution of at least three elements
for i in range(len(nums)):
head = nums[i]# It's also the first element
left = i + 1# Left pointer
right = len(nums) - 1# Right pointer
while(left<right):
sum = nums[left] + nums[right] + head# Sum up
if(abs(sum - target) < abs(answer - target)):# Comparison error
answer = sum# Optimal solution replacement
if(sum > target):# Greater than the target value , Right pointer left
right -= 1
elif(sum < target):# Less than the target value , Move the left pointer to the right
left += 1
else:
return answer
return answer
#196 ms 15.3 MB
# advantage ： Fast
# shortcoming ： It's not very intuitive , First of all, we should understand the routine of double pointer
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)
#24 ms 14.9 MB
# advantage ： Implement a simple , Speed is fine
# No algorithmic thinking ： It's easy to lose your job （doge）
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left = 0# The left pointer represents the index of the new array
for right in range(len(nums)):# Traverse the old array
if(nums[right]!=val):# If it is not the number to delete
nums[left] = nums[right]# Assign to new array
left += 1 # Add one to the new array
return left
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:
delete_num = []
for i in range(len(nums)-1):
if(nums[i]==nums[i+1]):
delete_num.append(nums[i])# Find the number of all the same numbers , Storage
for i in delete_num:# Delete one by one according to the list
nums.remove(i)
return len(nums)
#1112 ms 15.8 MB
# advantage ： Implement a simple
# Algorithmic thinking is not strong , Slower , It's easy to lose your job （doge）
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
index=0# The first index , Left pointer
for i in range(1,n):# The second index , Right pointer
if nums[index]==nums[i]:
continue
nums[index+1] = nums[i]# By default , The left pointer is smaller than the right pointer 1, This method does not change the contents of the array , If appear continue, be index Add less 1, Result in misaligned assignment .
index += 1# Left pointer plus 1, To repeat the number also add 1
return index+1
#32 ms 15.9 MB
# advantage ： Implement a simple
# shortcoming ： The idea of algorithm is difficult to understand .
