Why is my python code so slow (leetcode)? [duplicate]

Question

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        prev = []
        for i,j in enumerate(nums):
            if j in prev:
                nums[i] = -j
            else:
                prev.append(j)
        return sum(nums)

It's a question from leetcode and actually the one with highest AC rate. However, as my code goes, it tells me Time Limit Exceeded and could not been accepted. Could any one analyze my code including the complexity? Thank you so much.

Upadate: Thank you all and I have changed the "prev" from a list to a set, which works nicely!

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        prev = set([])
        for i,j in enumerate(nums):
            if j in prev:
                nums[i] = -j
            else:
                prev.add(j)
        return sum(nums)

However I am still looking for solutions that requires no extra memories as the question describes.

Update: I used another way trying to solve the problem but receives a Time Exceeded again.

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        for i,j in enumerate(nums):
            if j in set(nums[:i+1]):
                nums[i] = -j
        return sum(nums)

Actually I an kinda confused that does the slice like nums[:i+1] create a separate list every loop? So is the creation of list the most time consuming here? I used set instead of list so this may reduce the cost for searching.

Answer 1

@Peter's answer is brilliant:

def singleNumber(nums):
    unique = 0
    for num in nums:
        unique ^= num
    return unique