【C语言】数据结构基础（每日小细节025），有三数之和哦

算法好题初阶一共14回已经更新完毕从今天开始就是基础的数据结构题目 

1.只出现一次的数字 

 

如果不额外开辟任何空间的话一定要想到位运算符

异或^ :两个整数异或遵循相同为0相异为1的二进制位运算规则

1任何两个相同的数字异或之后都是0

2任何数字和0异或之后都是本身

3异或遵循结合律和交换律

知道这些之后这个题就变得尤为简单因为根据1所有数字里面成对出现的异或之后都是0,0和单身狗异或之后还是单身狗并且因为3所以我们上面分析的过程是正确的即使成对出现的数字不挨着交换之后还是对的

int singleNumber(int* nums, int numsSize){
int ans=0;
for(int i=0;i<numsSize;i++)
{
    ans^=nums[i];
}
return ans;
}

 

---

2.多数元素

 看到一个很有意思的解法 每个数字都代表了一个门派开始打擂台假设每个角色的攻击力一样那么1v1就是两个人都死擂台上无人count==0时那么直接站上去ans=nums【i】如果上来一个同门派nums【i】==ans那么人数++count++如果上来别的门派直接各死一个count--

int majorityElement(int* nums, int numsSize){
int ans=-1,count=0;
for(int i=0;i<numsSize;i++)
{
    if(count==0)
    {
        ans=nums[i];
        count+=1;
    }
    else if(nums[i]==ans)
    {
          count+=1;
    }
    else
    {
        count-=1;
    }
}
return ans;
}

---

3..三数之和

 三数之和是两数之和的进阶版

两数之和

两数之和是很简单的甚至暴力遍历也可以

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize=2;
int* tmp=(int*)malloc(sizeof(int)*2);
for(int i=0;i<numsSize;i++)
{
    for(int j=i+1;j<numsSize;j++)
    {
        if(nums[i]+nums[j]==target)
        {
            tmp[0]=i;
            tmp[1]=j;
            return tmp;
        }
    }
}
return NULL;
}

 三数之和就是一个进阶版首先暴力不能解决问题太显然了时间肯定超

那么还记得昨天更新的最后一天二叉搜索树里面的找两个节点的最近共同祖先其实一个思路昨天的思路不重复了今天的是首先把数组排序然后规定三个下标变量leftrightmid顾名思义left从0开始right从最后一个下标开始mid就是left的下一个然后开始计算三个数字的和如果sum<0,那么说明mid的值应该更大一点因为在我们的方法里left是最外层的循环right除了nums[right]==nums[--right]还有sum>0,否则也是不会变的所以只能mid向后走因为已经有序所以向后就是增大sum

同理如果sum>0就应该让right--,平衡sum

最后如果有和nums[left]重复的元素直接不遍历left返回for循环就可以

如果有和nums[mid]相同的元素mid++

如果有和nums[right]相等的元素right--

 int cmp(const void* a1,const void*b1)
 {
     return *(int*)a1-*(int*)b1;
 }
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
*returnSize=0;
if(numsSize<3) return NULL;
qsort(nums,numsSize,sizeof(int),cmp); //排序
int** ans=(int**)malloc(sizeof(int*)*numsSize*numsSize);
*returnColumnSizes=(int*)malloc(sizeof(int)*numsSize*numsSize);
int i,j,k,sum,left,right=0,mid=0;
for(left=0;left<numsSize-2;left++)
{
    if(nums[left]>0) return ans;
    if(left>0 && nums[left-1]==nums[left]) continue;
    mid=left+1;right=numsSize-1;
    while(mid<right)
    {
        sum=nums[left]+nums[right]+nums[mid];
        if(sum==0)
        {
            ans[*returnSize]=(int*)malloc(sizeof(int)*3);
            (*returnColumnSizes)[*returnSize]=3;
            ans[*returnSize][0]=nums[left];
            ans[*returnSize][1]=nums[mid];
            ans[*returnSize][2]=nums[right];
            *returnSize+=1;
            while(mid<right && nums[mid]==nums[++mid]);
            while(mid<right && nums[right]==nums[--right]);
        }
        else if(sum<0)
        {
            mid++;
        }
        else{
            right--;
        }
    }

}
return ans;
}

一定要注意二维数组的初始化,一定是数组大小的平方否则会栈溢出或者写一个可以扩容的也行但是这个题目的难点显然就不在这里所以比数组长度平方还大肯定没问题