Given a non-empty&nbsp;array of integers nums, every element appears twice except for one. Find that single one.

You must&nbsp;implement a solution with a linear runtime complexity and use&nbsp;only constant&nbsp;extra space.

&nbsp;
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 3 * 104
	-3 * 104 &lt;= nums[i] &lt;= 3 * 104
	Each element in the array appears twice except for one element which appears only once.


class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        i=0
        while i<len(nums)-1:
            if nums[i]==nums[i+1]:
                i+=2
            else:
                return nums[i]

        return nums[-1]
class Solution {
    public int singleNumber(int[] nums) {
        Stack numStack = new Stack();
        Arrays.sort(nums);
        for (var i = 0; i < nums.length; ++i) {
            numStack.push(nums[i]);
            if (i < nums.length - 1 && nums[++i] != (int) numStack.peek()) break;
        }
        return (int) numStack.pop();
    }
}
class Solution {
public:
    int singleNumber(vector<int>& nums) { 
       unordered_map<int,int> a;
	   for(auto x: nums)
		   a[x]++;
	   for(auto z:a)
		   if(z.second==1)
			   return z.first;
	   return -1;
    }
};
var singleNumber = function(nums) {
    let s = 0; // Location of first possible suspect
    for (let i = s + 1; i < nums.length; i++) {
        if (nums[i] == nums[s]) { // If we found a duplicate
            nums.splice(i, 1); // Remove duplicate so it won't confuse us next time we come across it
            s++; // Next suspect's location
            i = s; // Start of next search (i=s+1 in next loop iteration)
        }
    }
    return nums[s];
};
Single Number