Leetcode 01 array

Array

Preface ： In order to consolidate their python Basics , I use every optimal solution here python and java To write the .

Array storage

Array storage ：c Number of bytes of storage space occupied for each element

One dimensional array a[n]：Loc(a[i]) = Loc(a[0]) + i * c

Two dimensional array a[m, n]：Loc(a[i, j]) = Loc(a[0, 0]) + (i * n + j) * c

Three dimensional array a[m, n, l]：Loc(a[i, j, k]) = Loc(a[0, 0, 0]) + (i * n * l + j * l + k) * c

title

Sum of two numbers

1. Title Description

2. Solution ideas and code

• Simple approach ：O(n^2)

double for loop , Directly determine whether the sum of two subscripts is equal to target, Equal to the direct output result .

	public int[] twoSum(int[] nums, int target) {
    
        for (int i = 0; i < nums.length; i ++ ) {
    
            for (int j = i + 1; j < nums.length; j ++ ) {
    
                if (nums[i] + nums[j] == target)    return new int[]{
    i, j};
            }
        }
        return new int[]{
    0, 0};
    }

• Use hash table ：O(n)

Use HashMap Store data in a hash table , Traverse each element , Find whether the hash table contains target - x, If it contains a direct return result , Do not include continue traversal .

	public int[] twoSum(int[] nums, int target) {
    
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i ++ ) {
    
            if (map.containsKey(target - nums[i]))
                return new int[] {
    map.get(target - nums[i]), i};
            map.put(nums[i], i);
        }
        return new int[0];
    }

class Solution(object):
    def twoSum(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        map = dict()
        for i, num in enumerate(nums):
            if target - num in map:
                return [map[target - num], i]
            map[num] = i
        return []

The closest sum of three

1. Title Description

2. Solution ideas and code

• Simple approach ：O(n^3)

Triple cycle , Enumerate three numbers , Judge their sum and target The absolute value of , Returns the sum of the smallest absolute value

	public int threeSumClosest(int[] nums, int target) {
    
        int res = 0, subtract = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i ++ ) {
    
            for (int j = i + 1; j < nums.length; j ++ ) {
    
                for (int k = j + 1; k < nums.length; k ++ ) {
    
                    int tmp = nums[i] + nums[j] + nums[k];
                    if (Math.abs(tmp - target) < subtract) {
    
                        subtract = Math.abs(tmp - target);
                        res = tmp;
                    }
                }
            }
        }
        return res;
    }

• Sort + Double pointer ：O(n^2)

Sort the array , Enumerate the first element , Then enumerate the second and third elements with double pointers , Last result returned .

	public int threeSumClosest(int[] nums, int target) {
            
        Arrays.sort(nums);
        int best = nums[0] + nums[1] + nums[2];
        
        for (int i = 0; i < nums.length - 2; i ++ ) {
     
            int st = i + 1, ed = nums.length - 1;
            
            while(st < ed) {
    
                int sum = nums[i] + nums[st] + nums[ed];
                
                if (Math.abs(sum - target) < Math.abs(best - target)) {
    
                    best = sum;
                }
                
                if (sum < target)   st ++ ;
                else if (sum > target)  ed --;
                else    return best;
            }
        }
        return best;
    }

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

Remove elements

1. Title Description

2. Solution ideas and code

• Speed pointer ：O(n)

Use left Indicates the length of the last array ,right Determine whether the elements of an array are equal to val, It's not equal to val Put in left In the array that points to .

	public int removeElement(int[] nums, int val) {
    
        int l = 0, r = 0;
        while(r < nums.length) {
    
            if (nums[r] != val) {
    
                nums[l ++ ] = nums[r];
            }
            r ++ ;
        }
        return l;
    }

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[l] = nums[i]
                l += 1
        return l

Remove duplicate items from an ordered array

1. Title Description

2. Solution ideas and code

• Speed pointer ：O(n)

Use left Point to the far left of the array , Judge left and right Whether it is equal or not , If it is not equal, then right Put in left In the following elements , Finally back to left+1, Pay attention to when nums The array is 0 A special judgment is needed .

	public int removeDuplicates(int[] nums) {
    
        if (nums.length == 0)   return 0;
        int l = 0;
        for (int i = 1; i < nums.length; i ++ ) {
    
            if (nums[i] != nums[l]) {
    
                l ++ ;
                nums[l] = nums[i];
            }
        }
        return l + 1;
    }

Another way to do it ： Judge right and right-1 Whether the elements of are equal , If not, put in left in , then left++

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l = 0
        for i in range(len(nums)):
            if i == 0 or nums[i] != nums[i - 1]:
                nums[l] = nums[i]
                l += 1
        return l

Sum of three numbers

1. Title Description

2. Solution ideas and code

This problem is to get the specific array elements , Instead of array subscripts , Therefore, it is difficult to obtain the results by using the hash table . Here we first sort the array , Then determine the first element , Then determine the second element , The third element gets by default from the last element , Then judge the result and 0 The gap between , If big , Then back off .

And also notice that , Because we need to ensure that the same elements are the same result , So if the first element is the same as the previous element when it is cycled , There is no need to cycle , The second element requires the same judgment . Just make sure that the first element and the second element do not repeat , Then the final result must not be repeated .

	public List<List<Integer>> threeSum(int[] nums) {
    
        Arrays.sort(nums);
        
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        
        for (int i = 0; i < nums.length; i ++ ) {
    
            //  Make sure that the first element is not repeated 
            if (i > 0 && nums[i] == nums[i - 1])    continue;
            int k = nums.length - 1;
            for (int j = i + 1; j < nums.length; j ++ ) {
    
                //  Make sure that the second element is not repeated 
                if (j > i + 1 && nums[j] == nums[j - 1])    continue;
                while (nums[j] + nums[k] + nums[i] > 0 && j < k) k -- ;
                if (k == j) break;
                if (nums[j] + nums[k] + nums[i] == 0) {
    
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);
                }
            }
        }
        
        return ans;
    }

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