Searching for Items in an Array

本文蒐集

• LeetCode 1346
• LeetCode 941

LeetCode 1346: Check If N and Its Double Exist

Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exists two indices i and j such that :

• i != j
• 0 <= i, j < arr.length
• arr[i] == 2 * arr[j]

Example 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Example 2:

Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

Example 3:

Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.

Constraints:

• 2 <= arr.length <= 500
• -10^3 <= arr[i] <= 10^3

我的解法: 暴力兩層迴圈

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        for i in range(len(arr)):
            for j in range(len(arr)):
                if i != j and arr[i] == arr[j]*2:
                    return True
        return False

Time: O(\(n^2\)) Space: O(1)

LeetCode 941: Valid Mountain Array

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Example 1:

Input: arr = [2,1]
Output: false

Example 2:

Input: arr = [3,5,5]
Output: false

Example 3:

Input: arr = [0,3,2,1]
Output: true

Constraints:

• 1 <= arr.length <= \(10^4\)
• 0 <= arr[i] <= \(10^4\)

我的解法

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        i = 0
        j = len(arr)-1
        if len(arr) >= 3:
            for i in range(len(arr)-1):
                if arr[i] >= arr[i+1]:
                    break
            for j in range(len(arr)-1, 0, -1):    
                if arr[j-1] <= arr[j]:
                    break
            if i == j:
                return True
        return False

Time: O(n) Space: O(1)