[Leetcode Python problem solution] "1346. Check If N and Its Double Exist"

Topic:1346. Check If N and Its Double Exist

Question description

Given an array of integers arr, check if there are two different indexes i and j, satisfies:

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

Example

Example 1:

1
2
3

输入：arr = [10,2,5,3]
输出：true
解释：对于 i = 0 和 j = 2，arr[i] = 10 等于 2 * 5 = 2 * arr[j]

Example 2:

1
2
3

输入：arr = [3,1,7,11]
输出：false
解释：不存在满足条件的 i 和 j。

Constraints

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

Problem-solving ideas

This problem can be solved in many ways. Let's analyze the two main solutions: brute force solution and hash table solution.

1. Violent solution

The most intuitive solution is to use a two-level loop to traverse all possible number pairs.

1
2
3
4
5
6
7

def checkIfExist(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n):
            if i != j and arr[i] == 2 * arr[j]:
                return True
    return False

Complexity analysis:

• Time complexity: O(n²), where n is the array length
• Space complexity: O(1), only constant extra space used

2. Hash table solution

Using a hash table can significantly optimize the time complexity. We only need to traverse the array once and use a hash table to record the numbers we have encountered.

1
2
3
4
5
6
7

def checkIfExist(arr):
    seen = set()
    for num in arr:
        if num * 2 in seen or (num % 2 == 0 and num // 2 in seen):
            return True
        seen.add(num)
    return False

Complexity analysis:

• Time complexity: O(n), only needs to traverse the array once
• Space complexity: O(n), additional hash table space required

Code optimization case

Let's look at an initial version of the code and how to optimize it:

Original version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        hashmap = {}
        for i, item in enumerate(arr):
            hashmap[i] = item
            if item * 2 in hashmap.values():
                j = next(k for k, v in hashmap.items() if v == item * 2)
                if i != j:
                    return True
            if item//2 in hashmap.values() and item%2==0:
                j = next(k for k, v in hashmap.items() if v == item//2)
                if i != j:
                    return True
        return False

Optimized version:

1
2
3
4
5
6
7
8

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        seen = set()
        for num in arr:
            if num * 2 in seen or (num % 2 == 0 and num // 2 in seen):
                return True
            seen.add(num)
        return False

Optimization points

1. Data structure selection

   • Use sets instead of dicts
   • No need to store index information, only focus on the existence of values

2. code simplification

   • Merge duplicate checking logic
   • Remove unnecessary variables and calculations
   • Use more concise conditional judgment

3. Performance improvements

   • avoid using hashmap.values() Traverse
   • O(1) finding properties using sets
   • Reduce double counting

Key points to note

1. Boundary case handling

   • Consider the case where there are 0 in the array (twice 0 is still 0)
   • Pay attention to the handling of negative numbers
   • Make sure not to use the same index (i != j)

2. Numerical check

   • Need to check twice and half of a number at the same time
   • Make sure the number is even when checking half

3. Performance optimization

   • Use appropriate data structures (collections)
   • Avoid unnecessary calculations and traversals

Summary

This question shows how to improve algorithm performance by selecting appropriate data structures and optimizing code logic. From the initial brute force solution to the use of hash tables to the optimization of the code, each step has brought significant improvements. The final solution not only runs efficiently, but the code is concise and easy to understand.

The key is to understand:

1. Although the brute force solution is intuitive, it is inefficient
2. Hash tables provide optimal time and space trade-offs
3. Code optimization is not only for efficiency, but also for readability and maintainability