LeetCode-算法-双指针-第17天

82. 删除排序链表中的重复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。返回同样按升序排列的结果链表。

示例1：
输入：head = [1,2,3,3,4,4,5]
示例2:
输出：[1,2,5]
输入：head = [1,1,1,2,3]
输出：[2,3]

Python

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        node=ListNode(0,head)
        node1=node
        while head:
            while head.next and head.next.val==head.val:
                head=head.next
            if head==node.next:
                node=node.next
            else:
                node.next=head.next
            head=head.next
        return node1.next

思路：因为只要出现重复，那么就要全部删除。因此我们在比对过程中，需要存在一个在比对下标前的节点，当出现重复时去链接下一个不重复的节点。新创建一个node节点，使其指向head，因为我们不排除head节点也可能和其他元素重复，因此需要有个指向head节点来记录。
while head（此时的head相当于游标，不断向后移动）通过循环节点，进行head.next.val与head.val比对，若相同则证明需要剔除，但为了保证一次性全部剔除，则head=head.next，直到head.next.val!=head.val则停止循环，之后if head==node.next进行判断，head是否发生了移动，如果没有移动则应该相同，此时只需要node移动到下个节点，若不相同，则证明存在剔除，因此需要将node.next指向head.next。

GO

func deleteDuplicates(head *ListNode) *ListNode {
    if head==nil || head.Next==nil{
        return head
    }
    if head.Val==head.Next.Val{
        x:=head.Next
        for x!=nil && x.Val==head.Val{
            x=x.Next
        }
         return deleteDuplicates(x)
    }else{
        head.Next= deleteDuplicates(head.Next)
    }
    return head
}

思路：同python

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]

具体题目链接

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        length=len(nums)
        if not nums and length<3:
            return []
        nums.sort()#排序数组
        res=[]
        for i in range(length):
            if nums[i]>0:#大于0则直接返回，因为在循环中nums[i]为最小，若大于0，则三数之和必大于0
                return res
            if i>0 and nums[i]==nums[i-1]:#保证nums[i]不重复，重复则跳过，为保证不出现重复值。
                continue
            left,right=i+1,length-1#定义左右指针，通过挪动寻找结果
            while left<right:
                if nums[i]+nums[left]+nums[right]==0:
                    res.append([nums[i],nums[left],nums[right]])
                    #结果记录后，需要排除相同元素，直到指向最后一个
                    while left<right and nums[left]==nums[left+1]:
                        left+=1
                    while left<right and nums[right]==nums[right-1]:
                        right-=1
                    left+=1
                    right-=1
                elif nums[i]+nums[left]+nums[right]>0:
                    right-=1
                else:
                    left+=1
        return res

思路：这个看的一位大佬的思路，只是理解后学习了。整体细节考虑太多。

GO

func threeSum(nums []int) [][]int {
    length:=len(nums)
    if nums==nil || length<3{
        return [][]int{}
    }
    sort.Ints(nums)
    res:=[][]int{}
    for i:=0;i<length;i++{
        if nums[i]>0{
            return res
        }
        if i>0 && nums[i]==nums[i-1]{
            continue
        }
        left,right:=i+1,length-1
        for left<right{
            if nums[i]+nums[left]+nums[right]==0{
                res=append(res,[]int{nums[i],nums[left],nums[right]})
                for left<right && nums[left]==nums[left+1]{
                    left++
                }
                for left<right && nums[right]==nums[right-1]{
                    right--
                }
                left++
                right--
            }else if nums[i]+nums[left]+nums[right]>0{
                right--
            }else{
                left++
            }
        }
    }
    return res

}

思路：参考python