136. Single Number

Description

Given an array of integers, return the indices of the two numbers that add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Intuition

We can use a hashmap to store the complement of each number. As we iterate through the array, we check if the current number's complement exists in the hashmap.

Approach

1. Create an empty hashmap to store the complement and its index.
2. Iterate through the array: - Calculate the complement by subtracting the current number from the target. - If the complement exists in the hashmap, return the indices of the complement and the current number. - Otherwise, store the current number and its index in the hashmap.

Complexity

Time complexity:

O(n), where n is the length of the array.

Space complexity:

O(n), for the hashmap.

Code

C++

class Solution {
public:
    int singleNumber(vector& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (find(nums.begin(), nums.end(), nums[i]) == find(nums.rbegin(), nums.rend(), nums[i]).base() - 1) {
                return nums[i];
            }
        }
        return -1; // Should never reach here since the problem guarantees a solution
    }
};

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

Java

class Solution {
    public int singleNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    count++;
                }
            }
            if (count == 1) {
                return nums[i];
            }
        }
        return -1; // If no single number found
    }
}

JavaScript

var singleNumber = function (nums) {
    for (let i = 0; i < nums.length; i++) {
        if (nums.indexOf(nums[i]) === nums.lastIndexOf(nums[i])) {
            return nums[i];
        }
    }
};