找出所有子集的异或总和再求和

找出所有子集的异或总和再求和

暴力可以直接过，直接枚举所有子集情况

(1) dfs递归的求出每个子集

求出异或结果和，并加起来递归实现dfs，nums表示数组，i 表示枚举到的位置，xorSum表示已经累计的异或总和

递归内容，对于每个位置的元素都有加入或不加入子集，分别进行递归递归结束条件，枚举完所有位置 i == nums.length

(2)位运算求出每个子集，用二进制枚举

用一个长度为 n 的二进制数来表示所有的子集，每一位对应nums 的每一位取还是不取（1表示取，0表示不取）

这正好能够表示 nums 数组所有的子集情况（n 个数的子集个数为 2 ^ n）

再枚举这个二进制数的每一位，如果这一位为 1，那么将该位 nums 进行异或，最后将每种子集的结果累加即可

链表

环形链表

1、先要判断是否有环

判断是否有环，这个在环形链表I 当中使用fast指针每次移动两个结点和slow指针每次移动一个结点当两者相等时表示有环。

(fast相对slow指针相对运动，每次接近一个结点，直到重合，所以fast不会错过slow)

2、再找出环的入口位置

环的入口位置，新建一个指针从head开始移动和slow指针一起，每次移动一格，两者相遇结点即为环入口结点

证明：

设链表长度为 a + b，a为环入口距离(不包括链表入口结点)，b为环长度，f为fast指针，s为slow指针

f=2s（快指针每次2步，路程刚好2倍）

f = s + nb (相遇时，fast刚好多走了n圈）

推出相遇时slow指针走了：s = nb 从head结点走到入环点需要走： a + nb，而slow已经走了nb，那么slow再走a步就是入环点了

所以，从head开始，和slow指针一起走，相遇时刚好就是a步

双指针

双指针并不属于某一种数据结构，只是一种操作方法，所以我们在数组、链表、字符串中都用到了。

双指针之所以被使用，是因为他可以通过两个指针在一个for循环下实现两个for循环所做的事情。这样就极大的减少了运行时间，将时间复杂度由O(n^2)降为O(n)

双指针具体怎么用就要根据需求。

比如要是反转字符串：